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.

$\endgroup$
  • $\begingroup$ In the literature, I think it is more common to refer to this as 2-edge connected. $\endgroup$ – utdiscant Jun 16 '12 at 16:39
  • $\begingroup$ @utdiscant: very helpful comment. $\endgroup$ – caozhu Jun 17 '12 at 22:56
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.

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

Your Answer

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

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