Minimal spanning tree

[oren tal]

How can I design algoritem that check for a given Graph if a minimal spanning tree exist without a specific edge.

Mean that for the original graph you find a minimal spannig tree and that spanning tree not include the edge and it is minimal spanning tree of the graph that do include the edge.

The algorithm must run in O(|V| + |E|) when V - vertics and E - edge

:hihi:

I spent hours and have not find any solution yet!

[Buffy]

Its been a while since I've thought about graph traversal problems, but this looks like two problems in one. First of all, finding the minimum spanning tree(s), will give you all trees that have minimum spans, then you just need to test the given edge against those trees. Note you have to find all spans in order to identify the minimums, and the most obvious ones all require [math]O(n^2)[/math] time, although Wiki mentions (but does not link) to an algorithm by Bernard Chazelle that is supposedly [math]O(n log n)[/math]. That's still not the [math]O(n)[/math] implied by the problem you presented, and does not include the second step of checking the given edge against the solution set (which would be [math]O(n)[/math], [math]O(log n)[/math] or [math]O(1)[/math] depending on whether your data structure for graphs allowed linear, binary or hashed indexing.

 

Maybe I don't understand the problem though, so you might want to try to clarify it for us.

 

Getting from here to everywhere,

Buffy

[oren tal]

let my clearfy:

i want an algorithm which return Boolean answer.

input (G=graph, e=edge in G's edges)

true if MST exist for graph G. such that the MST don't containe THE edge e.

false otherwise

 

in O(V+E)

thanks alot

----------------------------

Kruskal's algorithm and Prim's algorithm are the more common algoritem!

-----------------------------------------------------------------

Anyway I hope now you can give me more direction I still :D

[Buffy]

Okay then I think I did understand. You are only given the graph and the edge, so the solution involves:

1. Find all MSTs for the given graph.
   
2. Check all those MSTs for the given edge.
   

A correction to what I mentioned above, the best you can do for step 1 according to the literature is [math]O(n)[/math] (see next paragraph). If you can build your data structure for your MSTs so that you can hash search for edges (this would probably be a tremendous waste of memory, but that's not a constraint is it?), then you could do step 2 in [math]O(1)[/math], so we can ignore that step.

 

The only constraint you have is that it run in "[math]O(e+v)[/math]" which is essentially equivalent to [math]O(n)[/math] (because [math](v-1 \leq e \leq (v\cdot(v-1))[/math] and therefore ends up being a constant for purposes of computing the Order of the algorithm). As a result, the afforementioned Chazelle algorithm, which is [math]O(n)[/math], will fill the bill, but all the more common ones all appear to be [math]O(n^2)[/math] (see previously mentioned Wiki page), so unless you can reinvent Prof. Chazelle's algorithm (or find it somewhere), or invent a never before discovered solution, then your trouble solving this one is not too hard to explain!

 

As I said before, I'm rusty on this, so don't take my word for it, and some of our other CS experts may tell me I'm out to lunch (won't be the first time! :rolleyes: )

 

Orderly algorithms,

Buffy