Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Sorry about my English.

G=(V,E}, directed graph without cycles. every edge has a weight. Two vertexes: x and y.

Defenition: Bottleneck edge in path P is defined to be the edge with minimum weight in P.

Legal solution: simple path between x and y.

I have to find an algorithm which is a Maximum Legal solution with bottleneck in $O(|V|+|E|)$.

I tried to think about a formula - OPT (j,t) - which t is the bottleneck's edge until Edge j. but I stuck to prove it (because t has to change during the algorithm).

Any ideas? Thank u!

share|improve this question
1  
Is your "Legal solution" a simple path between x and y, or is it a directed path from x to y? If you want to find a Maximum "Legal solution", what makes one path the Maximum? Is the problem to maximize the bottleneck's weight (a max-min problem)? – hardmath Mar 19 '11 at 13:54
I'm not sure that I unserstand. The path is dircted path between x and Y. I want to maximize the path that contain the bottleneck's edge. The problem is How to find this path, because in the algorithm, the bottlenexk's edge is changing all the time. – Amir Mar 19 '11 at 14:09
Okay, do you mean "maximize the path" to be the longest possible path (no retracing possible since the graph does not contain cycles)? Or perhaps maximum total weight? – hardmath Mar 19 '11 at 15:57
I think hardmath has it-find the path (directed from x to y) with maximum weight on the bottleneck. – Ross Millikan Mar 19 '11 at 16:13
I mean maximum total weight. Thank u – Amir Mar 19 '11 at 16:32
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.