FINDING BICONNECTED COMPONENTS IN O(N) TIME FOR A CLASS OF GRAPHS

A rooted tree is called a single-branch tree if there is exactly one n onleaf vertex on each level except the bottom level of the tree. We pr esent an O(n) time algorithm for finding biconnected components in a g raph 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 s how that such SBS trees can be found for the interval graphs and the p ermutation graphs in O(n) time. Hence, the biconnected components in t hese graphs can be obtained in O(n) time, while finding biconnected co mponents in a general graph of n vertices and m edges takes O(m + n) t ime.