A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks.
For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.

There are two ways to solve articulation point problems.

A) For every vertex v, do following

…..a) Remove v from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add v back to the graph

For this algorithm time complexity is O(V*(V+E))

B)Linear time algorithm :: Tarjan’s algorithm

Time complexity O(V+E).It is a DFS based solution. Articulation point connects two (or more) sub graphs. In a DFS tree a vertex u is articulation point iff it follows one of the following two rules.

a)u is root of DFS tree and it has at least two children.

b)If u is not root of DFS tree and it has a child v such that no vertex in sub tree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.


Leave a Reply

Your email address will not be published. Required fields are marked *