<p>Not sure what you are asking here, but I guarantee you won't find any sub-linear time algorithm for this task.</p>

<p>If you have $O(M+(N+M )) = O(N+M)$ algorithm,  be happy about it :).</p>

<p>In the general case, every set of two edges could leave the graph disconnected so you'd need $\Omega(M^2)$ just to output the result (think of a cycle on $N$ vertices).</p>

CC BY-SA 3.0
2014-01-10T13:38:47.420Z
N <= 100000 and M <= 300000
O( M + (N + M ) ) != O ( N + M ) I guarantee
cr.rusucosmin
CC BY-SA 3.0
2014-01-10T13:46:25.813Z
Hmm, I guess you misunderstand what the $O$ stands for (or possibly in the wrong forum).

No matter what are M,N values, $M+(N+M) = 2M + N < 2(M+N)$.

See here: http://en.wikipedia.org/wiki/Big_O_notation
R B
CC BY-SA 3.0
2014-01-10T13:49:33.473Z
Ahhh, I wrote O( M + (N + M ) ? Sorry, I ment O ( M * ( M + N ) )...I will edit the question as well. Sorry again!
cr.rusucosmin
CC BY-SA 3.0
2014-01-10T13:22:14.993Z
2014-01-10T14:01:35.020Z
2014-01-10T14:01:35.020Z
R B
<p>How to find ALL the pair of two edges which, removed from a graph, makes it disconnected?
I was thinking about a O(M * (N + M )) algorithm, and I am wondering if there is a better algorithm.
Thanks in advice!</p>

CC BY-SA 3.0
2014-01-13T09:32:52.000Z
Please check [about] and [help/on-topic]. This question seems more suitable for [cs.se] which has a broader scope.
Kaveh
<graph-theory><graph-algorithms>
How to find the pair of two of edges which, removed from a graph, makes it disconnected?
cr.rusucosmin
# How to find the pair of two of edges which, removed from a graph, makes it disconnected?

(Asked by: username_0 on 2014-01-10)

How to find ALL the pair of two edges which, removed from a graph, makes it disconnected?
I was thinking about a O(M \* (N + M )) algorithm, and I am wondering if there is a better algorithm.
Thanks in advice!

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Please check [about] and [help/on-topic]. This question seems more suitable for [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_2 on 2014-01-10. Score: 1

Not sure what you are asking here, but I guarantee you won't find any sub-linear time algorithm for this task.

If you have $O(M+(N+M )) = O(N+M)$ algorithm, be happy about it :).

In the general case, every set of two edges could leave the graph disconnected so you'd need $\Omega(M^2)$ just to output the result (think of a cycle on $N$ vertices).

> **Comments:**
> **username_0**: N <= 100000 and M <= 300000 O( M + (N + M ) ) != O ( N + M ) I guarantee  
> **username_2**: Hmm, I guess you misunderstand what the $O$ stands for (or possibly in the wrong forum).  No matter what are M,N values, $M+(N+M) = 2M + N < 2(M+N)$.  See here: http://en.wikipedia.org/wiki/Big_O_notation  
> **username_0**: Ahhh, I wrote O( M + (N + M ) ? Sorry, I ment O ( M * ( M + N ) )...I will edit the question as well. Sorry again!  

---

