3
$\begingroup$

Given a network as a directed acyclic graph with a source and sink, and non-negative edge capacities, I am interested in the extreme source-sink flows. More formally, I am interested in a characterization of the extreme points (vertices) of the capacitated flow polytope. Can someone provide me a reference to this problem or state the solution.

$\endgroup$
2
$\begingroup$

You can have a look at chapter 13, namely "Path and flow polyhedra and total unimodularity", of Alexander Schrijver's masterpiece "Combinatorial Optimization - Polyhedra and Efficiency". You will find characterizations based on cuts, which are the dual of flows in digraphs. This is linked to the famous max-flow min-cut theorem.

$\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.