Biconnected component
From Wikipedia, the free encyclopedia
A biconnected component in graph theory is a maximal biconnected subgraph.
[edit] Algorithms
The classic sequential algorithm for computing biconnected components in a connected graph due to John Hopcroft and Robert Tarjan (1971) runs in linear time, and is based on depth first search. Disjoint-set data structures provide an efficient online algorithm for computing dynamic biconnected components that can be updated as vertices or edges are added. Uzi Vishkin together with Robert Tarjan (1985) designed a parallel algorithm on CRCW PRAM that runs in O(log n) time with O(n+m) processors. Guojing Cong and David A. Bader (2005) developed an algorithm that achieves a speedup of 5 with 12 processors on SMPs [1].
[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:.
