A comparison of Steiner tree relaxations
From MaRDI portal
Publication:5946825
DOI10.1016/S0166-218X(00)00318-8zbMath0984.90051OpenAlexW2004305790WikidataQ127109995 ScholiaQ127109995MaRDI QIDQ5946825
Tobias Polzin, Siavash Vahdati Daneshmand
Publication date: 27 February 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00318-8
flow-class relaxationlinear programming relaxationsSteiner problem in networksSteiner tree relaxationstree-class relaxation
Related Items
ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ Optimization models for a single-plant district cooling system ⋮ Optimal Steiner trees under node and edge privacy conflicts ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ A branch-and-cut algorithm for the Steiner tree problem with delays ⋮ General network design: a unified view of combined location and network design problems ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ Vertex covering with capacitated trees ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ The Steiner connectivity problem ⋮ Algorithmic expedients for the prize collecting Steiner tree problem ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Integer programming for urban design ⋮ A multicast problem with shared risk cost ⋮ A partition-based relaxation for Steiner trees ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Steiner trees and polyhedra ⋮ Improved algorithms for the Steiner problem in networks ⋮ Capacitated ring arborescence problems with profits ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Approaches to the Steiner Problem in Networks ⋮ Multi-level Steiner Trees ⋮ Towards a lifecycle oriented design of infrastructure by mathematical optimization ⋮ Integer programming formulations for the shared multicast tree problem ⋮ Multi-Level Steiner Trees. ⋮ On Steiner trees and minimum spanning trees in hypergraphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Survivable networks, linear programming relaxations and the parsimonious property
- The Steiner tree problem
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- The Steiner tree problem. II: Properties and classes of facets
- Integer Programming Formulation of Traveling Salesman Problems
- A dual ascent approach for steiner tree problems on a directed graph
- Problem reduction methods and a tree generation algorithm for the steiner network problem
- An SST-based algorithm for the steiner problem in graphs
- An integer linear programming approach to the steiner problem in graphs
- Solving Steiner tree problems in graphs to optimality
- A catalog of steiner tree formulations
- Matroids and the greedy algorithm
- Improved algorithms for the Steiner problem in networks
