Biconnected ComponentsWhat are Biconnected Components of a Graph?An undirected graph is called biconnected if for every pair of nodesu and v there are two node disjoint paths between u
and v. To disconnect a biconnected graph you need to delete at least two nodes.
The biconnected components of an undirected graph are its maximal biconnected subgraphs.
What are Biconnected Components good for?Some graph algorithms only work for biconnected graphs. One method to apply such an algorithm to a graph that is not biconnected is to compute the biconnected components and apply the algorithm to each component separately. Example of how to compute biconnected components Running TimeThe running time is linear in the size of the graph (O(|V|+|E|)). |
See also:GraphWin for visualizing graphs and graph algorithms Manual Entries: |