A biconnected component (or 2-connected component) in graph theory is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components attached at shared vertices, which are cut vertices (also known as articulation points)—this structure is called the block tree of the graph.

Contents 1 Algorithm 2 Other Algorithms 3 See also 4 Notes 5 References

[edit] Algorithm

The classic sequential algorithm for computing biconnected components in a connected graph due to John Hopcroft and Robert Tarjan (1973) ^[1] runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 23-2 of Introduction to Algorithms (both 2nd and 3rd edition).

The idea is to run a depth-first search while maintaining the following information:

1. the depth of each vertex in the depth-first-search tree (once it gets visited), and
2. for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint.

The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of all neighbors of v (other than v's parent in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.

The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if v's lowpoint is at least as large as v's depth. This property can be tested once the lowpoint of v is computed (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of the descendants of v (by traversing the depth-first-search tree), and henceforth pretending that v had no children in the depth-first-search tree, so that the subgraph above v will not descend into v's ancestors.

The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children. Thus, it suffices to simply build one component out of each child subtree of the root (including the root).

[edit] Other Algorithms

In the online version of the problem, vertices and edges are added (but not removed) dynamically, and a data structure must maintain the biconnected components. Jeffery Westbrook and Robert Tarjan (1992) ^[2] developed an efficient data structure for this problem based on disjoint-set data structures. Specifically, its processes n vertex additions and m edge additions in O(mα(m,n)) total time, where α is the inverse Ackermann function. This time bound is proved to be optimal.

Uzi Vishkin and Robert Tarjan (1985) ^[3] designed a parallel algorithm on CRCW PRAM that runs in O(logn) time with O(n + m) processors. Guojing Cong and David A. Bader (2005) ^[4] developed an algorithm that achieves a speedup of 5 with 12 processors on SMPs.

[edit] See also

• Triconnected component

[edit] Notes

1. ^ Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272.  edit
2. ^ Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line". Algorithmica 7: 433–464. doi:10.1007/BF01758773.  edit
3. ^ Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM Journal on Computing 14: 862–000. doi:10.1137/0214061.  edit
4. ^ Guojing Cong and David A. Bader, (2005). "An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)". Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium. pp. 45b. doi:10.1109/IPDPS.2005.100.  edit

[edit] References

• Eugene C. Freuder (1985). "A Sufficient Condition for Backtrack-Bounded Search". Journal of the Association for Computing Machinery 32 (4): 755–761. doi:10.1145/4221.4225.