bridge in O(E) time?
Moderator: Board moderators
bridge in O(E) time?
Can anyone tell me how can i find the bridge(s) of a graph G in O(E) time.
Thanks in advance.
Naushad
Thanks in advance.
Naushad
bridge in O(E)
Dear Larry,
Sorry for late reply. First of all your statement is not clear to me. I need the bridges of the graph. Not if there any bridge or not. Next, if I apply DFS it is O(V+E), but i have the limitation of O(E).
Naushad
Sorry for late reply. First of all your statement is not clear to me. I need the bridges of the graph. Not if there any bridge or not. Next, if I apply DFS it is O(V+E), but i have the limitation of O(E).
Naushad
Larry is right. You can use a dfs for this. The actual name of this algorithm is finding "biconnected components". It is hard to explain here on the forum, but easy to implement. You will find nice sites about it on google. There is another algorithm for this which doesn't use recursion, but I don't know much about its complexity. I suspect that it's also O(E+V).

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could anyone tell me, what's wrong with my code ?
I post it under this link: http://acm.uva.es/board/viewtopic.php?t=1853
Thanks in advance
DM
I post it under this link: http://acm.uva.es/board/viewtopic.php?t=1853
Thanks in advance
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
I think most of this confusion is stemming from the close relationship between O(V+E) and O(E). For all practical purposes, they're the same, so sometime you'll see O(V+E) referred to as O(E) (which is technically a bit sloppy). The only way in which O(E) can be less than O(V) is if a graph has an asymptotically large number of isolated vertices.
If the input to an algorithm contains some explicit representation of vertices, and assuming the algorithm has to look at all it's input, then said algorithm must be Omega(V). The only case in which you could have an O(E) algorithm instead of an O(V+E) is if the isolated vertices aren't represented explicitly (either the vertices are numbered and all vertices from 1 to V are implicitly present, or a count of isolated vertices is given).
Personally, I think whoever asked you for an O(E) bridge algorithm was just being sloppy, and was actually looking for an O(V+E) algorithm. Isolated vertices have nothing to do with the bridges of a graph, so clearly they are not of interest. Lets assume you have been given the graph as a list of edges, each edge represented by an unordered pairs of integers.
case 1: the vertex indexes (assume a range of 1..V), are dense, that is to say: V is O(E). Then O(E) == O(V+E).
case 2: the vertex indexes are sparse, so their range is asymptotically larger than E. Then you need to do some work to identify edges which meet, e.g. sorting all the vertex indexes present or putting them in a tree, so you're stuck with O(E log E) now.
If you're looking at case 1, the O(E) / O(V+E) distinction is a red herring. If you're in case 2, you won't get an O(E) algorithm anyway. In general, the running time for any graph algorithm which takes a list of edges as input and examines them all is going to be Omega(min(V+E, E log E))
So I think there's some fundamental confusion at the root of this question.
If the input to an algorithm contains some explicit representation of vertices, and assuming the algorithm has to look at all it's input, then said algorithm must be Omega(V). The only case in which you could have an O(E) algorithm instead of an O(V+E) is if the isolated vertices aren't represented explicitly (either the vertices are numbered and all vertices from 1 to V are implicitly present, or a count of isolated vertices is given).
Personally, I think whoever asked you for an O(E) bridge algorithm was just being sloppy, and was actually looking for an O(V+E) algorithm. Isolated vertices have nothing to do with the bridges of a graph, so clearly they are not of interest. Lets assume you have been given the graph as a list of edges, each edge represented by an unordered pairs of integers.
case 1: the vertex indexes (assume a range of 1..V), are dense, that is to say: V is O(E). Then O(E) == O(V+E).
case 2: the vertex indexes are sparse, so their range is asymptotically larger than E. Then you need to do some work to identify edges which meet, e.g. sorting all the vertex indexes present or putting them in a tree, so you're stuck with O(E log E) now.
If you're looking at case 1, the O(E) / O(V+E) distinction is a red herring. If you're in case 2, you won't get an O(E) algorithm anyway. In general, the running time for any graph algorithm which takes a list of edges as input and examines them all is going to be Omega(min(V+E, E log E))
So I think there's some fundamental confusion at the root of this question.
Last edited by ChristopherH on Wed May 14, 2003 6:21 pm, edited 1 time in total.
I think you're not right, Christopher. I can put all nonisolated vertices in a queue while reading the input, and then run the dfs only from vertices that are in the queue. The dfs would have complexity O(E+V'), where V' is the size of the queue. V' is also at most two times more than E, so it can actually be O(E). One thing you are right about though: O(E) and O(E+V) are pretty much the same.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
O notation
I think Christopher is right. Lets look the definition of O notation.
f(x) = O(g(x)) if exists constant c and n0 > 0 such tath f(x) <= c.g(x) for any n >= n0.
Now lets see how many edges exists in a graph. In a complete graph with n vertex there are at most C(n, 2), or n choose 2, edges.
In that way we can see that E = O(V^2).
And for the definition of O notation:
O(V^2) = O(V^2 + V)
so
O(E) = O(E+V).
f(x) = O(g(x)) if exists constant c and n0 > 0 such tath f(x) <= c.g(x) for any n >= n0.
Now lets see how many edges exists in a graph. In a complete graph with n vertex there are at most C(n, 2), or n choose 2, edges.
In that way we can see that E = O(V^2).
And for the definition of O notation:
O(V^2) = O(V^2 + V)
so
O(E) = O(E+V).
[]'s
Lucindo
Lucindo