The minimum spanner problem on butterfly graphs
Resource
Parallel Architectures, Algorithms and Networks, 2000. I-SPAN 2000. Proceedings. International Symposium on
Journal
International Symposium on Parallel Architectures, Algorithms and Networks
Pages
-
Date Issued
2000-12
Date
2000-12
Author(s)
Hwang, Shien-Ching
DOI
N/A
Abstract
Given a connected graph G, a spanning subgraph G' of G is called a t-spanner if every pair of two adjacent vertices in G has a distance of at most t in G'. A t-spanner of a graph G is minimum if it contains minimum number of edges among all t-spanners of G. Finding minimum spanners for general graphs is rather difficult. Most of the previous results were obtained for some particular graphs, e.g., butterfly graphs, cube-connected cycles, de Bruijin graphs, Kautz graphs, complete bipartite graphs and permutation graphs. The butterfly graphs were originally introduced as the underlying graphs of FFT networks which can perform the fast Fourier transform (FFT) very efficiently. We successfully construct most of the minimum t-spanners for the k-ary r-dimensional butterfly graphs for 2/spl les/t/spl les/6 and t=8.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
00900287.pdf
Size
606.41 KB
Format
Adobe PDF
Checksum
(MD5):a15ced62fc82d6ded0d35833bd1089b7