A two-commodity cut theorem

Research output: Contribution to journalArticlepeer-review

14 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 languageEnglish (US)
Pages (from-to)177-181
Number of pages5
JournalDiscrete Mathematics
Volume23
Issue number2
DOIs
StatePublished - 1978
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A two-commodity cut theorem'. Together they form a unique fingerprint.

Cite this