Geodesic
Hamilton Decompositions and (n/2)-Factorizations of Hypercubes
Journal of Graph Algorithms and Applications, Tome 7 (2003) no. 1, pp. 79-98.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2003_7_1_a2,
     author = {Douglas Bass and I. Hal Sudborough},
     title = {Hamilton {Decompositions} and {(n/2)-Factorizations} of {Hypercubes}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {79--98},
     publisher = {mathdoc},
     volume = {7},
     number = {1},
     year = {2003},
     doi = {10.7155/jgaa.00061},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00061/}
}
TY  - JOUR
AU  - Douglas Bass
AU  - I. Hal Sudborough
TI  - Hamilton Decompositions and (n/2)-Factorizations of Hypercubes
JO  - Journal of Graph Algorithms and Applications
PY  - 2003
SP  - 79
EP  - 98
VL  - 7
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00061/
DO  - 10.7155/jgaa.00061
LA  - en
ID  - JGAA_2003_7_1_a2
ER  - 
%0 Journal Article
%A Douglas Bass
%A I. Hal Sudborough
%T Hamilton Decompositions and (n/2)-Factorizations of Hypercubes
%J Journal of Graph Algorithms and Applications
%D 2003
%P 79-98
%V 7
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00061/
%R 10.7155/jgaa.00061
%G en
%F JGAA_2003_7_1_a2
Douglas Bass; I. Hal Sudborough. Hamilton Decompositions and (n/2)-Factorizations of Hypercubes. Journal of Graph Algorithms and Applications, Tome 7 (2003) no. 1, pp. 79-98. doi : 10.7155/jgaa.00061. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00061/

Cité par Sources :