Chvátal-Gomory cuts for the Steiner tree problem

DOI10.1016/J.DAM.2020.12.016MaRDI QIDQ2659072zbMATHOpenAlexFDO

Authors Daniela Gaul, Daniel R. Schmidt

Publication date 25 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.12.016

zbMATH Keywords

partitionSteiner treeodd-hole inequalitiesgeneral integer cuts

Mathematics Subject Classification ID

Linear programming (90C05) Trees (05C05) Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Recommendations

• Steiner trees and polyhedra
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Publication:3484640
• Packing Steiner trees: Further facets
• The Steiner tree polytope and related polyhedra

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A catalog of steiner tree formulations
• A comparison of Steiner tree relaxations
• A dual ascent approach for steiner tree problems on a directed graph
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A partition-based relaxation for Steiner trees
• Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An integer linear programming approach to the steiner problem in graphs
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Edmonds polytopes and a hierarchy of combinatorial problems
• Fixed charge multicommodity network design using \(p\)-partition facets
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• Network loading problem: valid inequalities from 5- and higher partitions
• On Steiner trees and minimum spanning trees in hypergraphs
• On the spanning tree polyhedron
• Optimizing over the first Chvátal closure
• Outline of an algorithm for integer solutions to linear programs
• Packing rooted directed cuts in a weighted directed graph
• Solving Steiner tree problems in graphs to optimality
• Steiner tree approximation via iterative randomized rounding
• Steiner trees and polyhedra
• Stronger path‐based extended formulation for 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
• Thek-Steiner Ratio in Graphs
• Tree polytope on 2-trees
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• k-Partition-based facets of the network design problem

Cited in

(1)

• Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut

Describes a project that uses

Uses Software

• SteinLib

This page was built for publication: Chvátal-Gomory cuts for the Steiner tree problem

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