Tree polytope on 2-trees
From MaRDI portal
The class of 2-tree graphs is defined inductively as follows: start with a single edge and add nodes by joining them to the two endpoints of an existing edge. Many NP-complete problems on graphs are polynomial when restricted to this class of graphs. In particular, the Steiner Tree problem is linear time solvable on graphs in this class. It is this observation that motivates the authors main result: a linear characterization of the convex hull of the characteristic vectors of trees of 2-free graphs.
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
- 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
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- 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
(19)- On survivable network polyhedra
- Strong lower bounds for the prize collecting Steiner problem in graphs
- Steiner trees for hereditary graph classes
- Treetopes and their graphs
- Stronger MIP formulations for the Steiner forest problem
- Decomposition and dynamic cut generation in integer linear programming
- k-edge connected polyhedra on series-parallel graphs
- Trees with 2-reinforcement number three
- 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
- 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
- scientific article; zbMATH DE number 2204758 (Why is no real title available?)
- Steiner trees and polyhedra
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
- Non delayed relax-and-cut algorithms
- On the feedback vertex set polytope of a series-parallel graph
- The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
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)
