Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results

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.


Published in:
Mathematical Methods of Operations Research, 41, 3, 325-346
Year:
1995
Keywords:
Note:
PRO 95.06
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)