Hi Alex, Sorry for the delay. I forgot to check the discussion list.
The main references are theorem 2.24 in Jon Kleinberg's Ph.D thesis, Approximation Algorithms for Disjoint Path Problems, and Chapter 12, Approximation algorithms by Vijay Vazirani. Before briefly answering your question, I think it is necessary to make something more specific. Consider a directional graph G = (N,E) and a source-termination pair (s, t) with demand p. Each link e in E attaches a parameter referred to bandwidth B_e. We refer a flow as a sequence of links each of which receives a flow. The total flow over an edge cannot exceed its bandwidth. If the bandwidths are positive integers, we have the following interesting integral version of max-flow min cut theorem. The max-flow is fractionally realizable if and only if it is realizable by p flow paths each carrying one unit of flow. In the simplest case I have ever known, these flow paths can be constructed using augmenting paths （Ford-Fulkerson Algorithm） each carrying just one unit flow originated from source s. Its time complexity is O(Np). Best, Percy -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/ _______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
