2
$\begingroup$

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of G.

I know the basic idea is to build a DFS searching tree and then check each edge is not on a circle with DFS. Any help would be appreciated.

What I expect to see is a detailed algorithm description(especially the initialization of needed variables which is obscure sometimes), complexity analysis could be omitted.

Improve this question
$\endgroup$
2
  • $\begingroup$ In the literature, I think it is more common to refer to this as 2-edge connected. $\endgroup$
    – utdiscant
    Jun 16, 2012 at 16:39
  • $\begingroup$ @utdiscant: very helpful comment. $\endgroup$
    – caozhu
    Jun 17, 2012 at 22:56

1 Answer 1

Reset to default
5
$\begingroup$

A simple algorithm is the following:

Let $G = (V,E)$ be the graph you want to check for 2-connectivity.

For each edge $e = (x,y) \in E$, look if there is a path from $x$ to $y$ in $(V, E \setminus \{e\})$. If for some $e$, there is not such a path, the graph is not 2-edge connected. If there is such a path for each $e$, $G$ is 2-edge connected.

You should also note, that this algorithm is not the fastest, but very easy to understand. The path-finding part can be done using for example BFS or Dijkstra's Algorithm.

This article also shows a simple algorithm for testing 2-edge connectivity, which runs in linear time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You can improve this answer by outlining the algorithm given in the paper; links break. $\endgroup$
    – Raphael ♦
    Jun 17, 2012 at 13:44
  • $\begingroup$ It's exactly what I'm looking for, thanks! $\endgroup$
    – caozhu
    Jun 17, 2012 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.