Multicommodity flows in planar graphs

Haruko Okamura; P. D. Seymour

doi:10.1016/S0095-8956(81)80012-3

Multicommodity flows in planar graphs

Haruko Okamura, P. D. Seymour

Research output: Contribution to journal › Article › peer-review

211 Scopus citations

Abstract

Suppose that G is a graph, and (s_i, t_i) (1≤i≤k) are pairs of vertices; and that each edge has a real-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are realvalued demands. When is there a flow for each i, between s_i and t_i and of value q_i, 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 s₁,...,s_k, t₁,...t k are all on the boundary of the infinite face.

Original language	English (US)
Pages (from-to)	75-81
Number of pages	7
Journal	Journal of Combinatorial Theory, Series B
Volume	31
Issue number	1
DOIs	https://doi.org/10.1016/S0095-8956(81)80012-3
State	Published - Aug 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/S0095-8956(81)80012-3

Cite this

@article{647b7f9d6dbf48299d8b100bd6f71bac,

title = "Multicommodity flows in planar graphs",

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.",

author = "Haruko Okamura and Seymour, {P. D.}",

year = "1981",

month = aug,

doi = "10.1016/S0095-8956(81)80012-3",

language = "English (US)",

volume = "31",

pages = "75--81",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Multicommodity flows in planar graphs

AU - Okamura, Haruko

AU - Seymour, P. D.

PY - 1981/8

Y1 - 1981/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0000800781&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000800781&partnerID=8YFLogxK

U2 - 10.1016/S0095-8956(81)80012-3

DO - 10.1016/S0095-8956(81)80012-3

M3 - Article

AN - SCOPUS:0000800781

SN - 0095-8956

VL - 31

SP - 75

EP - 81

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

Multicommodity flows in planar graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this