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

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

0.00 Avg rating—0 Votes
Article ID: iaor19961748
Country: Germany
Volume: 41
Issue: 3
Start Page Number: 325
End Page Number: 346
Publication Date: May 1995
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , ,
Abstract:

The authors 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. The authors characterize the convex hull of the feasible solution set for the case p=2.

Reviews

Required fields are marked *. Your email address will not be published.