Solving Steiner tree problems in graphs to optimality

DOI<207::AID-NET5>3.0.CO;2-O 10.1002/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-OzbMath1002.90078OpenAlexW2155239253MaRDI QIDQ4540078

Alexander Martin, Thorsten Koch

Publication date: 21 July 2002

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199810)32:3<207::aid-net5>3.0.co;2-o

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm, Preprocessing Steiner problems from VLSI layout, Optimal capacitated ring trees, A branch and cut algorithm for the hierarchical network design problem, Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice, Benders decomposition of the passive optical network design problem, A robust and scalable algorithm for the Steiner problem in graphs, On exact solutions for the minmax regret spanning tree problem, Optimal Steiner trees under node and edge privacy conflicts, Designing and constructing networks under uncertainty in the construction stage: definition and exact algorithmic approach, Lagrangian and branch-and-cut approaches for upgrading spanning tree problems, Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem, ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design, Unnamed Item, Chvátal-Gomory cuts for the Steiner tree problem, On the Exact Solution of Prize-Collecting Steiner Tree Problems, A branch-and-cut algorithm for the Steiner tree problem with delays, The rainbow Steiner tree problem, Optimizing splitter and fiber location in a multilevel optical FTTH network, Optimal connected subgraphs: Integer programming formulations and polyhedra, Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic, A linear programming based approach to the Steiner tree problem with a fixed number of terminals, A branch-and-cut algorithm for the connected max-\(k\)-cut problem, Steiner tree packing revisited, Solving Steiner trees: Recent advances, challenges, and perspectives, New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems, A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints, Vertex covering with capacitated trees, Robust capacitated Steiner trees and networks with uniform demands, Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm, Thinning out Steiner trees: a node-based model for uniform edge costs, SCIP-Jack -- a solver for STP and variants with parallelization extensions, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, The Steiner connectivity problem, Coordinated cutting plane generation via multi-objective separation, The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm, Tree network design avoiding congestion, A note on the generalized Steiner tree polytope, Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem, A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems, Delay-related secondary objectives for rectilinear Steiner minimum trees., Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs, Mathematical Programming Algorithms for Spatial Cloaking, A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints, Strong Steiner Tree Approximations in Practice, Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems, Stronger MIP formulations for the Steiner forest problem, Learning in Combinatorial Optimization: What and How to Explore, A Lagrangean-based decomposition approach for the link constrained Steiner tree problem, Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing, The Steiner tree problem with delays: a compact formulation and reduction procedures, The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm, Optimal design of hierarchical networks with free main path extremes, Reduction tests for the prize-collecting Steiner problem, An Exact Algorithm for the Steiner Forest Problem, A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems, Decomposition methods for the two-stage stochastic Steiner tree problem, Mixed-integer programming approaches for the time-constrained maximal covering routing problem, Exact methods for solving the elementary shortest and longest path problems, Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View, Binary Steiner trees: structural results and an exact solution approach, Solving minimum-cost shared arborescence problems, An algorithmic framework for the exact solution of tree-star problems, Viral systems: A new bio-inspired optimisation approach, MIP models for connected facility location: a theoretical and computational study, A comparison of Steiner tree relaxations, Improved algorithms for the Steiner problem in networks, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation, Mathematical methods for physical layout of printed circuit boards: an overview, Reformulations and solution algorithms for the maximum leaf spanning tree problem, Towards optimizing the deployment of optical access networks, A branch-and-cut algorithm for the maximum covering cycle problem, Implications, conflicts, and reductions for Steiner trees, Implications, conflicts, and reductions for Steiner trees, Generalized network design problems., SteinLib, Approaches to the Steiner Problem in Networks, Combinatorial optimization in system configuration design, Strong lower bounds for the prize collecting Steiner problem in graphs, Mixed-integer programming approaches for the tree \(t^*\)-spanner problem, The dynamic predicate stashing copy problem and the Steiner problem in graphs, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, On Steiner trees and minimum spanning trees in hypergraphs, Exact approaches for solving robust prize-collecting Steiner tree problems, Dimensioning multicast-enabled communications networks, Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem