TY - GEN
T1 - Efficient parallel algorithms for finding biconnected components of some intersection graphs
AU - Liang, Y.
AU - Dhall, S. K.
AU - Lakshmivarahan, S.
N1 - Publisher Copyright:
© 1991 ACM.
PY - 1991/4/1
Y1 - 1991/4/1
N2 - Finding biconnected components (BCs) of graphs is one of the fundamental problems in graph theory which has many practical applications. If n and m are the number of the nodes and edges, respectively, in graph G, finding the BCs takes O (log2n) time using n2/log2n processors on CREW model [19, 20]. The algorithm is optimal in the sense that the best sequential algorithm requires 0(m + n) time. In this paper, we present efficient parallel algorithms for finding BCs of interval graphs, circular-arc graphs and permutation graphs, which are subclasses of the class of intersection graphs. The algorithms, when implemented on CREW model, take O (logn) time using n processors for interval and circular-arc graphs, and using n2 processors for permutation graphs.
AB - Finding biconnected components (BCs) of graphs is one of the fundamental problems in graph theory which has many practical applications. If n and m are the number of the nodes and edges, respectively, in graph G, finding the BCs takes O (log2n) time using n2/log2n processors on CREW model [19, 20]. The algorithm is optimal in the sense that the best sequential algorithm requires 0(m + n) time. In this paper, we present efficient parallel algorithms for finding BCs of interval graphs, circular-arc graphs and permutation graphs, which are subclasses of the class of intersection graphs. The algorithms, when implemented on CREW model, take O (logn) time using n processors for interval and circular-arc graphs, and using n2 processors for permutation graphs.
UR - http://www.scopus.com/inward/record.url?scp=33746292756&partnerID=8YFLogxK
U2 - 10.1145/327164.327204
DO - 10.1145/327164.327204
M3 - Conference article
AN - SCOPUS:33746292756
SN - 0897913825
SN - 9780897913829
T3 - CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science
SP - 48
EP - 52
BT - CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science
PB - Association for Computing Machinery, Inc
T2 - 19th Annual Conference on Computer Science, CSC 1991
Y2 - 4 March 1991 through 7 March 1991
ER -