Given a graph $G$ and two vertices $s$ and $t$, I want the maximum flux path from $s$ to $t$.That is, imagine $G$ to be a flow network with capacities on the edges. I want to find a single path that can carry the maximum flow between $s$ and $t$.

Note that this is not the same as the maximum flow problem where you can compute flows from multiple paths.

Can someone point me to fast algorithms for computing the max flux path?


closed as off topic by Jeffε, Tsuyoshi Ito, Kaveh Jan 29 '13 at 6:28

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ i.e. you want a path P from A to B with the least-weight edge in P having maximum possible value. $\endgroup$ – Kaveh Jan 22 '13 at 2:54
  • 2
    $\begingroup$ This is a standard undergraduate homework exercise. $\endgroup$ – Jeffε Jan 28 '13 at 5:53
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. $\endgroup$ – Kaveh Jan 29 '13 at 6:29

The problem is known as "Maximum capacity path problem" or "Widest path problem"

See the original paper: T. C. Hu, "The Maximum Capacity Route Problem", Operations Research Vol. 9, No. 6 (Nov. - Dec., 1961), pp. 898-900

or the linear time algorithm described in: A. P. Punnen, "A linear time algorithm for the maximum capacity path problem" (but I didn't download/read it)


Not the answer you're looking for? Browse other questions tagged or ask your own question.