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.

Published on : Friday 24 October 2014