This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201.

Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion disconnects G.

Given : Graph (undirected) $G = (V,E)$

Find : A vertex not an articulation vertex

Here is how i tried. I know a brute force way to solve the problem. A1 is the brute force algorithm given below.

Algorithm A1

  1. Pick a vertex say $v$.
  2. Delete the vertex temporarily from $G$ (say $G'$ is a new graph).
  3. Run DFS on $G'$.
  4. If graph $G'$ is connected return (V).
  5. Else repeat (step 1 to step 4) for all vertice of $G$.

Runtime : $O(V(V + E))$

For better running time algorithm i tried to come up with a claim.

My Claim : A vertex is an not articulation vertex if in a DFS tree it involves in a back edge.

If the above claim is true then i only need to run the DFS algorithm once that means running time $O(V + E)$. So I have two questions 1) Is the claim correct 2) find an efficient algorithm which runs in $O(V + E)$. time.

  • $\begingroup$ What do you mean with the word "involves"? $\endgroup$ – adrianN Feb 2 '17 at 8:40
  • $\begingroup$ Yes but previously i assume that node u is not a root node of DFS tree $\endgroup$ – user35837 Feb 2 '17 at 11:06
  • $\begingroup$ @sameerkn Normally, yes. Unless there's some context that implies that a different meaning is intended. $\endgroup$ – David Richerby Feb 2 '17 at 11:21
  • $\begingroup$ @sameerkn i have given an algorithm of same time complexity in the questio n .if you know an efficient algorithm please write in answer. $\endgroup$ – user35837 Feb 2 '17 at 11:40
  • 1
    $\begingroup$ Tarjan's algorithms grows a DFS tree. A node is not an articulation point iff it has a back edge from a subtree to a node above. Special rule for the root. $\endgroup$ – Hendrik Jan Feb 2 '17 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy