Loading...
research article
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.
Type
research article
Authors
Publication date
1995
Published in
Volume
41
Issue
3
Start page
325
End page
346
Note
PRO 95.06
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record