Preprint, October 2017.

Abstract:

Let G be an edge-weighted planar graph with 2kterminal verticess_{1},t_{1}, ...,s,_{k}t. The_{k}minimum-sum vertex-disjoint pathsproblem asks for a set of pairwise vertex-disjoint simple paths of minimum total length, where theith path connectssto_{i}t. Even when all terminals lie on a single face, efficient algorithms for this problem are known only for fixed_{i}k≤3. We describe the first polynomial-time algorithm for the case of four arbitrary terminal pairs on a single face.

Publications - Jeff Erickson (jeffe@illinois.edu) 05 Apr 2018