Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00061 Hamilton Decompositions and (n/2)-Factorizations of Hypercubes Douglas W. Bass and I. Hal Sudborough Vol. 7, no. 1, pp. 79-98, 2003. Regular paper Abstract Since Qn, the hypercube of dimension n, is known to have n link-disjoint paths between any two nodes, the links of Qn can be partitioned into multiple link-disjoint spanning subnetworks, or factors. We seek to identify factors which efficiently simulate Qn, while using only a portion of the links of Qn. We seek to identify (n/2)-factorizations, of Qn where 1) the factors have as small a diameter as possible, and 2) mappings (embeddings) of Qn to each of the factors exist, such that the maximum number of links in a factor corresponding to one link in Qn (dilation), is as small as possible. In this paper we consider two algorithms for generating Hamilton decompositions of Qn, and three methods for constructing (n/2)-factorizations of Qn for specific values of n. The most notable (n/2)-factorization of Qn results in two mutually isomorphic factors, each with diameter n + 2, where an embedding exists which maps Qn to each of the factors with constant dilation.
|
Revised: September 2002. Submitted: November 2001. Revised: February 2003. Communicated by Balaji Raghavachari |
| Journal of Graph Algorithms and Applications |