# Graph - path with Bottleneck

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!

-
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