Biconnected component

Biconnected component

A biconnected component in graph theory is a maximal biconnected subgraph.

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

References

Search another word or see Biconnected componenton Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;