Chvátal-Gomory cuts for the Steiner tree problem

DOI10.1016/J.DAM.2020.12.016zbMATH Open1464.05039OpenAlexW3116506665MaRDI QIDQ2659072FDOQ2659072

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

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

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)

Cites Work

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

Cited In (1)

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

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)