Tree polytope on 2-trees

DOI10.1007/BF01582065MaRDI QIDQ1322553zbMATH OpenFDO

Authors François Margot, A. Prodon, 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) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Recommendations

• On trees of polygons
• Trees in Polyhedral Graphs
• The polyhedral tree complex
• The 2-radius and 2-radiian problems on trees
• A classification of plane and planar 2-trees
• The 2-dimension of a tree
• scientific article; zbMATH DE number 2204758
• Two-graphs and trees
• On the \((2,2)\)-domination number of trees
• Trees whose 2-domination subdivision number is 2

Cites work

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

Cited in

(18)

• An Exact Algorithm for the Steiner Forest Problem
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Steiner trees and polyhedra
• scientific article; zbMATH DE number 2204758 (Why is no real title available?)
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• Stronger MIP formulations for the Steiner forest problem
• Chvátal-Gomory cuts for the Steiner tree problem
• Non delayed relax-and-cut algorithms
• On survivable network polyhedra
• On the feedback vertex set polytope of a series-parallel graph
• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• \(k\)-edge connected polyhedra on series-parallel graphs
• Treetopes and their graphs
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Trees with 2-reinforcement number three
• Decomposition and dynamic cut generation in integer linear programming

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322553)