Minimum spanners of butterfly graphs.
Journal
Networks
Journal Volume
37
Journal Issue
3
Pages
156-164
Date Issued
2001
Author(s)
Hwang, Shien-Ching
Abstract
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 previous results were obtained for some particular graphs, for example, butterfly graphs, cube‐connected cycles, de Bruijn 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. In this paper, we successfully construct most of the minimum t ‐spanners for the k ‐ary r ‐dimensional butterfly graphs for 2 ≤ t ≤ 6 and t = 8. © 2001 John Wiley & Sons, Inc.
Type
journal article