Tree polytope on 2-trees

DOI10.1007/BF01582065zbMath0807.90118MaRDI QIDQ1322553

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

Publication date: 5 May 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

2-tree graphsSteiner Tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (14)

On the feedback vertex set polytope of a series-parallel graph ⋮ Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ Decomposition and dynamic cut generation in integer linear programming ⋮ On survivable network polyhedra ⋮ Steiner trees and polyhedra ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ Strong lower bounds for the prize collecting Steiner problem in graphs ⋮ \(k\)-edge connected polyhedra on series-parallel graphs ⋮ Non delayed relax-and-cut algorithms

Cites Work

• Unnamed Item
• Generalized Steiner problem in outerplanar networks
• Fast heuristic algorithms for rectilinear Steiner trees
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Steiner trees with \(n\) terminals among \(n+1\) nodes
• Steiner trees, partial 2–trees, and minimum IFI networks
• A dual ascent approach for steiner tree problems on a directed graph
• An integer linear programming approach to the steiner problem in graphs
• Faster exact algorithms for steiner trees in planar networks
• Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
• The steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs

This page was built for publication: Tree polytope on 2-trees