Biconnected component
Encyclopedia
In graph theory
, a biconnected component (or 2-connected component) is a maximal biconnected
subgraph. Any connected
graph decomposes into a tree of biconnected components called the block tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or articulation points. Specifically, a cut vertex is any vertex that when removed increases the number of connected components
.
and Robert Tarjan
(1973) runs in linear time, and is based on depth-first search
. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms
(both 2nd and 3rd editions).
The idea is to run a depth-first search while maintaining the following information:
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 v, the depth of all neighbors of v (other than the parent of v 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 there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (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 every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.
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).
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) developed an efficient data structure for this problem based on disjoint-set data structure
s. Specifically, it 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) 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a biconnected component (or 2-connected component) is a maximal biconnected
Biconnected graph
In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.In other words, a biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected.The property of being 2-connected...
subgraph. Any connected
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
graph decomposes into a tree of biconnected components called the block tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or articulation points. Specifically, a cut vertex is any vertex that when removed increases the number of connected components
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
.
Algorithm
The classic sequential algorithm for computing biconnected components in a connected undirected graph due to John HopcroftJohn Hopcroft
John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
and Robert Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
(1973) runs in linear time, and is based on depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms
Introduction to Algorithms
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities. It is also one of the most commonly cited references for algorithms in published papers, with over 4600...
(both 2nd and 3rd editions).
The idea is to run a depth-first search while maintaining the following information:
- the depth of each vertex in the depth-first-search tree (once it gets visited), and
- 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 v, the depth of all neighbors of v (other than the parent of v 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 there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (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 every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.
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).
Other algorithms
In the onlineOnline algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
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
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
(1992) developed an efficient data structure for this problem based on disjoint-set data structure
Disjoint-set data structure
In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
s. Specifically, it 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
Uzi Vishkin
Uzi Vishkin is a computer scientist at the University of Maryland, College Park, where he is Professor of Electrical and Computer Engineering at the University of Maryland Institute for Advanced Computer Studies . Uzi Vishkin is known for his work in the field of parallel computing...
and Robert Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
(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
David A. Bader
David A. Bader is a Professor and Executive Director of High-Performance Computing in the Georgia Tech College of Computing. In addition, Bader was selected as the director of the first Sony Toshiba IBM Center of Competence for the Cell Processor at the Georgia Institute of Technology...
(2005) developed an algorithm that achieves a speedup of 5 with 12 processors on SMPs.