next up previous contents index CD CD Algorithms
Next: Modeling Graph Problems Up: Applications of Graph Traversal Previous: Topological Sorting

Articulation Vertices

Figure: An articulation vertex is the weakest point in the graph  

Suppose you are a terrorist seeking to disrupt the telephone network. Which station in Figure gif should you choose to blow up to cause the maximum amount of damage? An articulation vertex is a vertex of a connected graph whose deletion disconnects the graph. Any graph that contains an articulation vertex is inherently fragile, because deleting that single vertex causes a loss of connectivity.   

In general, the connectivity of a graph is the smallest number of vertices whose deletion will disconnect the graph. For graphs with an articulation vertex, the connectivity is one. Connectivity is an important measure of robustness in network design, as discussed in catalog Section gif.   

A simple application of either depth-first or breadth-first search suffices to find all the articulation vertices in a graph in O(n (m+n)). For each vertex v, delete it and then do a BFS traversal of the remaining graph to establish whether it is still connected. In fact, there is a clever O(n+m) algorithm that tests all the vertices using only a single depth-first search. Additional information on edge and vertex connectivity testing appears in Section gif.

Mon Jun 2 23:33:50 EDT 1997