Finding biconnected components in O(n) time for a class of graphs

✍ Scribed by Y.Daniel Liang; Chongkye Rhee

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 460 KB
• Volume: 60
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00153-6

✦ Synopsis

A rooted tree is called a single-branch tree if there. is exactly one nonleaf vertex on each level except the bottom level of the tree. We present an O(n) time algorithm for finding biconnected components in a graph G, assuming that a single-branch breadth-first search (SBS) tree of any connected induced subgraph of G can be found in O(n) time. We show that such SBS trees can be found for the interval graphs and the permutation graphs in O(n) time. Hence, the biconnected components in these graphs can be obtained in O(n) time, while finding biconnected components in a general graph of n vertices and m edges takes O(m + n) time.