Multicommodity flows in planar graphs

Haruko Okamura, P. D. Seymour

Research output: Contribution to journalArticle

183 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)75-81
Number of pages7
JournalJournal of Combinatorial Theory, Series B
Volume31
Issue number1
DOIs
StatePublished - Aug 1981

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Multicommodity flows in planar graphs'. Together they form a unique fingerprint.

  • Cite this