L. Gardner, Comput. Sci. Program, Univ. of Texas at Dallas, Richardson, TX, USA
Z. Miller, Comput. Sci. Program, Univ. of Texas at Dallas, Richardson, TX, USA
D. Pritikin, Comput. Sci. Program, Univ. of Texas at Dallas, Richardson, TX, USA
I.H. Sudboroughl, Comput. Sci. Program, Univ. of Texas at Dallas, Richardson, TX, USA
Among Cayley graphs on the symmetric group, some that have a noticeably low diameter relative to the number of generators involved are the pancake network, burnt pancake network and cycle prefix network. Another such Cayley graph is the star network, and constructions have been given for one-to-one and one-to-many low dilation embeddings of hypercubes into star networks. For each of dilations 1 through 4, we construct embeddings of hypercube (and hypercube-like) networks into pancake, burnt pancake, cycle prefix and substring reversal networks. Our focus is on embeddings of hypercubes into pancake networks, the other results being closely related.
Index Terms:
hypercube networks; graph theory; group theory; hypercube embedding; Cayley graphs; symmetric group; graph diameter; generators; pancake network; burnt pancake network; cycle prefix network; substring reversal network; star network; low dilation embeddings
Citation:
L. Gardner, Z. Miller, D. Pritikin, I.H. Sudboroughl, "Embedding hypercubes into pancake, cycle prefix and substring reversal networks," hicss, pp.537, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb