Abstract
Suppose that (s1, t1),...,(sk, tk) are pairs of vertices of a graph. When can one choose a path between s1 and t1 for each i, all pairwise edge-disjoint? Menger's theorem answers this when s1,...,sk, t1,...,tk take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases. 1. (i) when k = 2, and 2. (ii) when s1,...,sk, t1,...,tk take only three distinct values-the solution to this is obtained by applying a theorem of Mader. We obtain both good characterizations and good algorithms for these problems. The analogous "vertex-disjoint" problems are also solved.
Original language | English (US) |
---|---|
Pages (from-to) | 293-309 |
Number of pages | 17 |
Journal | Discrete Mathematics |
Volume | 29 |
Issue number | 3 |
DOIs | |
State | Published - 1980 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics