A General Method for Efficient Embeddings of Graphs into Optimal Hypercubes
作者： Volker Heun , Ernst W. Mayr
关键词:
摘要: Embeddings of several graph classes into hypercubes have been widely studied. Unfortunately, almost all investigated are regular graphs such as meshes, complete trees, pyramids. In this paper, we present a general method for one-to-one embedding irregular their optimal based on extended-edge-bisectors graphs. An extended-edge-bisector is an edge-bisector with the additional property that subset vertices distributed more or less evenly among two halves bisected graph. The dilation and congestion depends quality extended-edge-bisector. Moreover, if extended bisection can be efficiently computed hypercube, so embedding.
springer.com
core.ac.uk
sci-hub.st 参考文章(23)
Charles H. Goldberg, Douglas B. West, Bisection of Circle Colorings Siam Journal on Algebraic and Discrete Methods. ,vol. 6, pp. 93- 106 ,(1985) , 10.1137/0606010
X.J. Shen, Q. Hu, W.F. Liang, Embedding K -ary complete trees into hypercubes Journal of Parallel and Distributed Computing. ,vol. 24, pp. 100- 106 ,(1995) , 10.1006/JPDC.1995.1010
A. Wagner, D. G. Corneil, Embedding trees in a hypercube is NP-complete SIAM Journal on Computing. ,vol. 19, pp. 570- 590 ,(1990) , 10.1137/0219038
Volker Heun, Ernst W. Mayr, A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube Journal of Algorithms. ,vol. 20, pp. 375- 399 ,(1996) , 10.1006/JAGM.1996.0018
F. T. Leighton, Mark J. Newman, Abhiram G. Ranade, Eric J. Schwabe, Dynamic tree embeddings in butterflies and hypercubes SIAM Journal on Computing. ,vol. 21, pp. 639- 654 ,(1992) , 10.1137/0221039
A. Wagner, D.G. Corneil, On the complexity of the embedding problem for hypercube related graphs Discrete Applied Mathematics. ,vol. 43, pp. 75- 95 ,(1993) , 10.1016/0166-218X(93)90170-S
Kemal Efe, Embedding mesh of trees in the hypercube Journal of Parallel and Distributed Computing. ,vol. 11, pp. 222- 230 ,(1991) , 10.1016/0743-7315(91)90046-C
Mee Yee Chan, Embedding of grids into optimal hypercubes SIAM Journal on Computing. ,vol. 20, pp. 834- 864 ,(1991) , 10.1137/0220052
M.Y. Chan, F. Chin, C.N. Chu, W.K. Mak, Dilation-5 Embedding of 3-Dimensional Grids into Hypercubes Journal of Parallel and Distributed Computing. ,vol. 33, pp. 98- 106 ,(1996) , 10.1006/JPDC.1996.0029
I. Havel, P. Liebl, One-legged caterpillars span hypercubes Journal of Graph Theory. ,vol. 10, pp. 69- 77 ,(1986) , 10.1002/JGT.3190100110