Disjoint Paths in Graphs

  • Date: 12/13/2007

Bruce Shepherd (McGill University)


University of Victoria


We consider the well-known edge-disjoint path problem (EDP) where we
are given a graph G and pairs of nodes (“demands”) s1t1, s2t2, . . .
sktk. A subset F of {1, 2, . . . , k} is routable if there exists |F|
edge-disjoint paths in G that connect the pairs siti for each i 2 F. We
analyze the problem of finding a maximum (weight) routable subset F.
The situation where G is a tree already includes several classical
combinatorial optimization problems such as the knapsack and b-matching
problems. We discuss what is known for this problem in the three cases
where G is a tree, a planar graph, or a general graph. Several open
problems will arise en-route.

Other Information: 

Special PIMS Lectures at UVIC 2007