Binary Steiner trees: structural results and an exact solution approach

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

zbMATH Keywords

integer programmingpolytopeSteiner treedegree constraintSteiner ratiobranch-\&-cut

Mathematics Subject Classification ID

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

• SCIP
• SteinLib
• Concorde
• MrBayes
• DIMACS
• Balibase
• SCIP-Jack

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