3
$\begingroup$

Is there any algorithm that can orient undirected graph G(V,E) (i.e., assign directions to edges) to achieve maximum flow in the network? Any suggestion?

$\endgroup$
3
$\begingroup$

I assume you are given an undirected network $G$, and two vertices $s,t$, and you wish to maximize the flow from $s$ to $t$, while directing the edges of $G$. In this case, you can just use the normal Ford-Fulkerson algorithm with the following modification:

Every time you take an augmenting $s$-$t$ path in $G$ and send flow along it, direct the edges along the path. Eventually, your algorithm will stop, and all edges (except those with flow 0) will have a direction. The flow will be maximal, which can be proven using the max-flow-min-cut theorem.

$\endgroup$
2
$\begingroup$

One of the most amazing theorems in graph theory is Nash-William's :

http://en.wikipedia.org/wiki/Strong_orientation

.... And its proof is constructive, but not that easy to implement :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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