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
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