A two-commodity cut theorem

P. D. Seymour

doi:10.1016/0012-365X(78)90116-4

A two-commodity cut theorem

P. D. Seymour

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

15 Scopus citations

Abstract

We prove that if s, s^′, t, t^′ are vertices of a graph, and no path of fewer than k edges joins s to s^′ or t to t^′, then there are 2k sets of edges, each meeting every path from s to s^′ and from t to t^′, such that no edge is in more than two of them. This result is dual to Hu's two-commodity flow theorem.

Original language	English (US)
Pages (from-to)	177-181
Number of pages	5
Journal	Discrete Mathematics
Volume	23
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(78)90116-4
State	Published - 1978
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(78)90116-4

Cite this

@article{4cbbe0f4ea8446f2b4ebeeb34db4d74d,

title = "A two-commodity cut theorem",

abstract = "We prove that if s, s′, t, t′ are vertices of a graph, and no path of fewer than k edges joins s to s′ or t to t′, then there are 2k sets of edges, each meeting every path from s to s′ and from t to t′, such that no edge is in more than two of them. This result is dual to Hu's two-commodity flow theorem.",

author = "Seymour, \{P. D.\}",

year = "1978",

doi = "10.1016/0012-365X(78)90116-4",

language = "English (US)",

volume = "23",

pages = "177--181",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A two-commodity cut theorem

AU - Seymour, P. D.

PY - 1978

Y1 - 1978

N2 - We prove that if s, s′, t, t′ are vertices of a graph, and no path of fewer than k edges joins s to s′ or t to t′, then there are 2k sets of edges, each meeting every path from s to s′ and from t to t′, such that no edge is in more than two of them. This result is dual to Hu's two-commodity flow theorem.

AB - We prove that if s, s′, t, t′ are vertices of a graph, and no path of fewer than k edges joins s to s′ or t to t′, then there are 2k sets of edges, each meeting every path from s to s′ and from t to t′, such that no edge is in more than two of them. This result is dual to Hu's two-commodity flow theorem.

UR - https://www.scopus.com/pages/publications/0012526283

UR - https://www.scopus.com/pages/publications/0012526283#tab=citedBy

U2 - 10.1016/0012-365X(78)90116-4

DO - 10.1016/0012-365X(78)90116-4

M3 - Article

AN - SCOPUS:0012526283

SN - 0012-365X

VL - 23

SP - 177

EP - 181

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

A two-commodity cut theorem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this