TY - GEN
T1 - Parallel decomposition of distance-hereditary graphs
AU - Hsieh, Sun yuan
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - A distance-Hereditary graph G has a binary tree representation called a decomposition tree. Given a decomposition tree, many graph-theoretical problems can be efficiently solved on G using the binary tree contraction technique. In this paper, we present an algorithm to construct a decomposition tree in O(log2 n) time using O(n+m) processors on a CREW PRAM, where n and m are the number of vertices and edges of G, respectively.
AB - A distance-Hereditary graph G has a binary tree representation called a decomposition tree. Given a decomposition tree, many graph-theoretical problems can be efficiently solved on G using the binary tree contraction technique. In this paper, we present an algorithm to construct a decomposition tree in O(log2 n) time using O(n+m) processors on a CREW PRAM, where n and m are the number of vertices and edges of G, respectively.
UR - https://www.scopus.com/pages/publications/84957697236
UR - https://www.scopus.com/pages/publications/84957697236#tab=citedBy
U2 - 10.1007/3-540-49164-3_40
DO - 10.1007/3-540-49164-3_40
M3 - Conference contribution
AN - SCOPUS:84957697236
SN - 3540656413
SN - 9783540656418
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 417
EP - 426
BT - Parallel Computation - 4th International ACPC Conference Including Special Tracks on Parallel Numerics (ParNum 1999) and Parallel Computing in Image Processing, Video Processing, and Multimedia, Proceedings
A2 - Zinterhof, Peter
A2 - Vajteršic, Marian
A2 - Uhl, Andreas
PB - Springer Verlag
T2 - 4th International ACPC Conference on Parallel Computation, ACPC 1999
Y2 - 16 February 1999 through 18 February 1999
ER -