Binary Steiner trees: structural results and an exact solution approach
From MaRDI portal
Publication:1751166
DOI10.1016/j.disopt.2016.05.006zbMath1387.90141OpenAlexW2469753241MaRDI QIDQ1751166
Susanne Pape, Frauke Liers, Alexander Martin
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2016.05.006
Programming involving graphs or networks (90C35) Trees (05C05) Problems related to evolution (92D15) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\), SCIP-Jack -- a solver for STP and variants with parallelization extensions, Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm, Mixed-integer programming techniques for the connected max-\(k\)-cut problem
Uses Software
Cites Work
- On some network design problems with degree constraints
- SCIP: solving constraint integer programs
- The Steiner problem in phylogeny is NP-complete
- Graph theory applications
- The Steiner tree problem
- The Steiner tree polytope and related polyhedra
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- The Steiner tree problem. II: Properties and classes of facets
- Thinning out Steiner trees: a node-based model for uniform edge costs
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
- Shortest connectivity. An introduction with applications in phylogeny.
- A branch and cut method for the degree-constrained minimum spanning tree problem
- Improved Algorithm for Degree Bounded Survivable Network Design Problem
- Survivable Network Design with Degree or Order Constraints
- Additive Guarantees for Degree-Bounded Directed Network Design
- Lower and upper bounds for the degree-constrained minimum spanning tree problem
- Odd Minimum Cut Sets and b-Matchings Revisited
- Steiner problem in networks: A survey
- Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
- Solving the Steiner Tree Problem on a Graph Using Branch and Cut
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- A branch and cut algorithm for the Steiner problem in graphs
- Solving Steiner tree problems in graphs to optimality
- The computation of nearly minimal Steiner trees in graphs
- Low-Degree Spanning Trees of Small Weight
- Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion
- Many birds with one stone
- A catalog of steiner tree formulations
- Steiner Minimal Trees
- The steiner problem in graphs
- Approximation algorithms for degree-constrained minimum-cost network-design problems
- A comparison of Steiner tree relaxations
- Benchmarking optimization software with performance profiles.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
