0
$\begingroup$

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?

$\endgroup$
  • 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
6
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$

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