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 -