We present an O(p*n) algorithm for the problem of finding disjoint simple paths of minimum total length between p given pairs of terminals on oriented partial 2-trees with n nodes and positive or negative arc lengths. The algorithm is in O(n) if all terminals are distinct nodes. We characterize the convex hull of the feasible solution set for the case p = 2.
Etienne Michel François Bamas, Lars Rohwedder
Mikhail Kapralov, Jakab Tardos
Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes