Implications, conflicts, and reductions for Steiner trees

DOI10.1007/978-3-030-73879-2_33zbMath1483.90144OpenAlexW3164642279MaRDI QIDQ5918437

Thorsten Koch, Daniel Rehfeldt

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-73879-2_33

zbMATH Keywords

exact solutionSteiner tree problembranch-and-cutreduction techniques

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Faster exact solution of sparse maxcut and QUBO problems, Implications, conflicts, and reductions for Steiner trees

Uses Software

• SCIP
• SteinLib
• CPLEX
• GeoSteiner
• SCIP-Jack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An edge elimination test for the Steiner problem in graphs
• The Steiner tree problem
• A robust and scalable algorithm for the Steiner problem in graphs
• Thinning out Steiner trees: a node-based model for uniform edge costs
• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• On Steiner trees and minimum spanning trees in hypergraphs
• Faster algorithm for optimum Steiner trees
• Approaches to the Steiner Problem in Networks
• Reduction tests for the steiner problem in grapsh
• Solving Steiner tree problems in graphs to optimality
• Preprocessing Steiner problems from VLSI layout
• Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
• Reducibility among Combinatorial Problems
• Practical Partitioning-Based Methods for the Steiner Problem
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Implications, conflicts, and reductions for Steiner trees
• A comparison of Steiner tree relaxations
• Improved algorithms for the Steiner problem in networks