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

DOI10.1007/BF01432363zbMath0838.90128MaRDI QIDQ4845143

Alain Prodon, Margot, François, Thomas M. Liebling

Publication date: 30 May 1996

Published in: [https://portal.mardi4nfdi.de/entity/Q4289815 ZOR Zeitschrift f�r Operations Research Mathematical Methods of Operations Research] (Search for Journal in Brave)

zbMATH Keywords

polyhedral characterizationdisjoint simple paths of minimum total lengthoriented partial 2-trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (1)

Tree polytope on 2-trees

Cites Work

• Unnamed Item
• Unnamed Item
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The directed subgraph homeomorphism problem
• Steiner trees, partial 2–trees, and minimum IFI networks
• Polyhedral Characterization of Discrete Dynamic Programming
• Characterization and Recognition of Partial 3-Trees
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Linear-time computation of optimal subgraphs of decomposable graphs
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results