Disjoint paths, multiflows, and applications in chip design
Jens Vygen, Professor,University of Bonn, Bonn, Germany.
Many applications (including routing problems) can be modeled by vertex- or edge-disjoint paths in directed or undirected graphs. The resulting optimization problems are NP-hard in general, but can be solved efficiently in some special cases. Otherwise the fractional relaxation (multiflows) often helps. I will explain why, what distinguishes it from single-commodity flows, and how to solve it. I will also discuss real-world applications to the layout of digital chips.