Biconnected component

Biconnected component

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


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


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