TY - GEN
T1 - A general method for efficient embeddings of graphs into optimal hypercubes
AU - Heun, Volker
AU - Mayr, Ernst W.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - Embeddings of several graph classes into hypercubes have been widely studied. Unfortunately, almost all investigated graph classes are regular graphs such as meshes, complete trees, pyramids. In this paper, we present a general method for one-to-one embedding irregular graphs into their optimal hypercubes based on extended-edge-bisectors of graphs. An extended-edge-bisector is an edge-bisector with the additional property that a subset of the vertices is distributed more or less evenly among the two halves of the bisected graph. The dilation and congestion of the embedding depends on the quality of the extended-edge-bisector. Moreover, if the extended bisection can be efficiently computed on the hypercube, so can the embedding.
AB - Embeddings of several graph classes into hypercubes have been widely studied. Unfortunately, almost all investigated graph classes are regular graphs such as meshes, complete trees, pyramids. In this paper, we present a general method for one-to-one embedding irregular graphs into their optimal hypercubes based on extended-edge-bisectors of graphs. An extended-edge-bisector is an edge-bisector with the additional property that a subset of the vertices is distributed more or less evenly among the two halves of the bisected graph. The dilation and congestion of the embedding depends on the quality of the extended-edge-bisector. Moreover, if the extended bisection can be efficiently computed on the hypercube, so can the embedding.
UR - http://www.scopus.com/inward/record.url?scp=0000900901&partnerID=8YFLogxK
U2 - 10.1007/3-540-61626-8_29
DO - 10.1007/3-540-61626-8_29
M3 - Conference contribution
AN - SCOPUS:0000900901
SN - 9783540616269
SN - 9783540616269
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 222
EP - 233
BT - Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings
A2 - Bouge, Luc
A2 - Fraigniaud, Pierre
A2 - Mignotte, Anne
A2 - Robert, Yves
A2 - Bouge, Luc
A2 - Fraigniaud, Pierre
A2 - Mignotte, Anne
A2 - Robert, Yves
PB - Springer Verlag
T2 - 2nd International European Conference on Parallel Processing, Euro-Par 1996
Y2 - 26 August 1996 through 29 August 1996
ER -