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. Journal articles
  4. Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
 
Loading...
Thumbnail Image
research article

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

Margot, François
•
Prodon, Alain
•
Liebling, Thomas M.  
1995
Mathematical Methods of Operations Research

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
  • Metrics
Type
research article
DOI
10.1007/BF01432363
Author(s)
Margot, François
•
Prodon, Alain
•
Liebling, Thomas M.  
Date Issued

1995

Published in
Mathematical Methods of Operations Research
Volume

41

Issue

3

Start page

325

End page

346

Subjects

2-tree

•

disjoint paths

•

polyhedral characterization

Note

PRO 95.06

Peer reviewed

REVIEWED

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