Improved algorithms for the Steiner problem in networks
From MaRDI portal
The paper gives several new techniques for dealing with the Steiner problem in networks. Certain relaxations of integer programming formulations are presented. Different methods for dealing these relaxations yield lower bounds and additional information which is used in computation of upper bounds and in reduction techniques. The authors modify some known reduction tests and introduce some new ones. On the basis of the new concept of heuristic reductions heuristics are developed that achieve good upper bounds and running times. A Lagrangean relaxation and the above procedures are integrated into an exact algorithm. Computational results demonstrate the superiority of this algorithm to other ones.
Recommendations
Cites work
- A branch and cut algorithm for the Steiner problem in graphs
- 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 faster approximation algorithm for the Steiner problem in graphs
- An algorithm for the steiner problem in graphs
- An integer linear programming approach to the steiner problem in graphs
- An SST-based algorithm for the steiner problem in graphs
- Applications of Path Compression on Balanced Trees
- Computing near‐optimal solutions to the steiner problem in a graph using a genetic algorithm
- Efficient path and vertex exchange in steiner tree algorithms
- scientific article; zbMATH DE number 758733 (Why is no real title available?)
- scientific article; zbMATH DE number 857591 (Why is no real title available?)
- scientific article; zbMATH DE number 1424547 (Why is no real title available?)
- On implementing the push-relabel method for the maximum flow problem
- Path-distance heuristic for the Steiner problem in undirected networks
- Reduction tests for the steiner problem in grapsh
- Solving Steiner tree problems in graphs to optimality
- Solving the Steiner Tree Problem on a Graph Using Branch and Cut
- Some generalizations of the steiner problem in graphs
- Steiner's problem in graphs: Heuristic methods
- Survivable networks, linear programming relaxations and the parsimonious property
- The Steiner tree problem
- The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
Cited in
(39)- A robust and scalable algorithm for the Steiner problem in graphs
- 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
- An exact solution framework for the minimum cost dominating tree problem
- On Steiner trees and minimum spanning trees in hypergraphs
- Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems
- Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
- Reduction tests for the prize-collecting Steiner problem
- Worst-case performance of Wong's Steiner tree heuristic
- Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice
- Optimality cuts and a branch-and-cut algorithm for the k-rooted mini-max spanning forest problem
- Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
- The influence of preprocessing on Steiner tree approximations
- Approaches to the Steiner Problem in Networks
- scientific article; zbMATH DE number 1982172 (Why is no real title available?)
- Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
- Strong Steiner tree approximations in practice
- Preprocessing Steiner problems from VLSI layout
- On the Exact Solution of Prize-Collecting Steiner Tree Problems
- A dual ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems
- A distributed dual ascent algorithm for Steiner problems in multicast routing
- Distance transformation for network design problems
- A partition-based relaxation for Steiner trees
- Strong Formulations for 2-Node-Connected Steiner Network Problems
- scientific article; zbMATH DE number 2230205 (Why is no real title available?)
- Implications, conflicts, and reductions for Steiner trees
- Implications, conflicts, and reductions for Steiner trees
- Steiner trees and polyhedra
- A comparison of Steiner tree relaxations
- 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
- NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
- A multicast problem with shared risk cost
- Designing a road network for hazardous materials shipments
- Mathematical methods for physical layout of printed circuit boards: an overview
- Reformulations and solution algorithms for the maximum leaf spanning tree problem
This page was built for publication: Improved algorithms for the Steiner problem in networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946826)
