bridge in O(E) time?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
naushad
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

bridge in O(E) time?

Post by naushad »

Can anyone tell me how can i find the bridge(s) of a graph G in O(E) time.
Thanks in advance.
Naushad

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Use DFS, which is linear, and then check for backedges. If there's no back edges, then it's a bridge.

naushad
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

bridge in O(E)

Post by naushad »

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

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet »

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).

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

Post by junjieliang »

The fastest method I know of is also dfs with O(V+E). If you ever find one that runs in O(E) or faster (and I hope you do :lol: ) could you post it on this board? Thanks.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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
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)

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

Post by junjieliang »

Thanks Dominik,

I went to check CLR and sure enough there is supposed to be an O(E) way of finding bridges. But the method that I know of happens to be O(V+E)!

I'll think about this and reply to the board if I can sort it out :wink:

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by ChristopherH »

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.
Last edited by ChristopherH on Wed May 14, 2003 6:21 pm, edited 1 time in total.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet »

I think you're not right, Christopher. I can put all non-isolated 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. :wink:

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

Post by junjieliang »

Thanks, Christopher and Makbet. It's much clearer now.

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

O notation

Post by lucindo »

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).
[]'s

Lucindo

Post Reply

Return to “Algorithms”