Steiner's problem in graphs: Heuristic methods

DOI10.1016/0166-218X(92)90021-2zbMath0758.68032OpenAlexW2117937654MaRDI QIDQ1201819

Stefan Voß

Publication date: 17 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90021-2

zbMATH Keywords

approximation algorithmSteiner treeexperimental comparison

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

A robust and scalable algorithm for the Steiner problem in graphs ⋮ Optimal Steiner trees under node and edge privacy conflicts ⋮ Combined column-and-row-generation for the optimal communication spanning tree problem ⋮ A heuristic for the Steiner problem in graphs ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ A note on distributed multicast routing in point-to-point networks ⋮ Steiner trees and polyhedra ⋮ Improved algorithms for the Steiner problem in networks ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ Combinatorial optimization in system configuration design ⋮ Generalized spanning trees ⋮ Worst-case performance of some heuristics for Steiner's problem in directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On efficient implementation of an approximation algorithm for the Steiner tree problem
• Combinatorial heuristic algorithms with FORTRAN
• Worst-case performance of Rayward-Smith's Steiner tree heuristic
• An edge elimination test for the Steiner problem in graphs
• A fast algorithm for Steiner trees
• Path-distance heuristic for the Steiner problem in undirected networks
• 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
• On finding steiner vertices
• Steiner problem in networks: A survey
• 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
• Une heuristique pour le problème de l'arbre de Steiner
• The computation of nearly minimal Steiner trees in graphs
• An algorithm for the steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs