Efficient parallel algorithms for finding biconnected components of some intersection graphs

Y. Liang, S. K. Dhall, S. Lakshmivarahan

Research output: Contribution to book or proceedingConference articlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationCSC 1991 - Proceedings of the 19th Annual Conference on Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages48-52
Number of pages5
ISBN (Print)0897913825, 9780897913829
DOIs
StatePublished - Apr 1 1991
Event19th Annual Conference on Computer Science, CSC 1991 - San Antonio, United States
Duration: Mar 4 1991Mar 7 1991

Publication series

NameCSC 1991 - Proceedings of the 19th Annual Conference on Computer Science

Conference

Conference19th Annual Conference on Computer Science, CSC 1991
Country/TerritoryUnited States
CitySan Antonio
Period03/4/9103/7/91

Fingerprint

Dive into the research topics of 'Efficient parallel algorithms for finding biconnected components of some intersection graphs'. Together they form a unique fingerprint.

Cite this