Loading...
report
Node disjoint paths of minimum total lenght on 2-trees
1988
The problem of finding p(and even 2) node disjoint paths on a digraph, connecting p pair of terminals is NP-complete. For directed k-trees however, the problem is polynomial. In this paper, we give a linear algorithm for the corresponding optimisation problem on 2-trees and for the case p=2, we characterize te convex hull of the corresponding edge incidence vectors. The optimization algorithm ramains linear and independent of p for k > or equal 3 if the terminals are distinct
Type
report
Authors
Publication date
1988
Note
PRO 88.05, No dates
Written at
EPFL
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record