Improved algorithms for the Steiner problem in networks
From MaRDI portal
Publication:5946826
DOI10.1016/S0166-218X(00)00319-XzbMath0994.90135OpenAlexW2008534472MaRDI QIDQ5946826
Siavash Vahdati Daneshmand, Tobias Polzin
Publication date: 30 July 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00319-x
Related Items
Preprocessing Steiner problems from VLSI layout, Optimality cuts and a branch-and-cut algorithm for the \(k\)-rooted mini-max spanning forest problem, Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice, A robust and scalable algorithm for the Steiner problem in graphs, Designing a road network for hazardous materials shipments, The Influence of Preprocessing on Steiner Tree Approximations, On the Exact Solution of Prize-Collecting Steiner Tree Problems, Matheuristics: survey and synthesis, Approximation algorithms for Steiner forest: An experimental study, A linear programming based approach to the Steiner tree problem with a fixed number of terminals, Solving Steiner trees: Recent advances, challenges, and perspectives, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, 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, Strong Steiner Tree Approximations in Practice, Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems, Reduction tests for the prize-collecting Steiner problem, Decomposition methods for the two-stage stochastic Steiner tree problem, Solving minimum-cost shared arborescence problems, An algorithmic framework for the exact solution of tree-star problems, A multicast problem with shared risk cost, A partition-based relaxation for Steiner trees, Worst-case performance of Wong's Steiner tree heuristic, Steiner trees and polyhedra, A comparison of Steiner tree relaxations, A distributed dual ascent algorithm for Steiner problems in multicast routing, Mathematical methods for physical layout of printed circuit boards: an overview, Reformulations and solution algorithms for the maximum leaf spanning tree problem, An exact solution framework for the minimum cost dominating tree problem, Implications, conflicts, and reductions for Steiner trees, Implications, conflicts, and reductions for Steiner trees, Approaches to the Steiner Problem in Networks, Distance Transformation for Network Design Problems, Unnamed Item, Strong Formulations for 2-Node-Connected Steiner Network Problems, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, 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 symmetric traveling salesman problem and edge exchanges in minimal 1- trees
- Path-distance heuristic for the Steiner problem in undirected networks
- Steiner's problem in graphs: Heuristic methods
- The Steiner tree problem
- On implementing the push-relabel method for the maximum flow problem
- Applications of Path Compression on Balanced Trees
- A dual ascent approach for steiner tree problems on a directed graph
- Some generalizations of the steiner problem in graphs
- An SST-based algorithm for the steiner problem in graphs
- Reduction tests for the steiner problem in grapsh
- An integer linear programming approach to the steiner problem in graphs
- Solving the Steiner Tree Problem on a Graph Using Branch and Cut
- Efficient path and vertex exchange in steiner tree algorithms
- A branch and cut algorithm for the Steiner problem in graphs
- Solving Steiner tree problems in graphs to optimality
- Computing near‐optimal solutions to the steiner problem in a graph using a genetic algorithm
- A catalog of steiner tree formulations
- An algorithm for the steiner problem in graphs
- A faster approximation algorithm for the Steiner problem in graphs
- A comparison of Steiner tree relaxations
