Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
1995
Abstract
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.
Details
Title
Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
Author(s)
Margot, François ; Prodon, Alain ; Liebling, Thomas M.
Published in
Mathematical Methods of Operations Research
Volume
41
Issue
3
Pages
325-346
Date
1995
Keywords
Note
PRO 95.06
Laboratories
ROSO
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > ROSO - Chair of Operations Research SO
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date
2006-02-13