Suppose that G is a graph, and (si, ti) (1≤i≤k) are pairs of vertices; and that each edge has a real-valued capacity (≥0), and that qi≥0 (1≤i≤k) are realvalued demands. When is there a flow for each i, between si and ti and of value qi, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s1,...,sk, t1,...t k are all on the boundary of the infinite face.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics