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

Special PIMS Lectures at UVIC 2007