Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. Node disjoint paths of minimum total lenght on 2-trees
 
report

Node disjoint paths of minimum total lenght on 2-trees

Margot, F.
•
Prodon, A.
•
Liebling, Th. M.  
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

  • Details
  • Metrics
Type
report
Author(s)
Margot, F.
Prodon, A.
Liebling, Th. M.  
Date Issued

1988

Note

PRO 88.05, No dates

Written at

EPFL

EPFL units
ROSO  
Available on Infoscience
February 13, 2006
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/222550
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés