Improved algorithms for the Steiner problem in networks

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

zbMATH Keywords

networkgraphSteiner problemheuristicexact algorithmreduction test

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (37)

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

• SteinLib
• OR-Library

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

This page was built for publication: Improved algorithms for the Steiner problem in networks