The computation of nearly minimal Steiner trees in graphs

DOI10.1080/0020739830140103zbMath0512.05024OpenAlexW2082150701MaRDI QIDQ4750659

V. J. Rayward-Smith

Publication date: 1983

Published in: International Journal of Mathematical Education in Science and Technology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/0020739830140103

Mathematics Subject Classification ID

Trees (05C05) Algorithms in computer science (68W99)

Related Items (25)

A primal-dual approximation algorithm for the Steiner forest problem ⋮ Models of greedy algorithms for graph problems ⋮ Steiner problem in Halin networks ⋮ 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 ⋮ Distributed multicast routing in point-to-point networks ⋮ Worst-case performance of Rayward-Smith's Steiner tree heuristic ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ The Steiner problem with edge lengths 1 and 2 ⋮ Minimum cost multicast routing using ant colony optimization algorithm ⋮ Strong Steiner Tree Approximations in Practice ⋮ Branch-and-bound as a higher-order function ⋮ Path-distance heuristic for the Steiner problem in undirected networks ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ A series of approximation algorithms for the acyclic directed Steiner tree problem ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Heuristics for the Steiner problem in graphs ⋮ Steiner's problem in graphs: Heuristic methods ⋮ FLOODING COUNTRIES AND DESTROYING DAMS ⋮ The full Steiner tree problem ⋮ Using structured steiner trees for hierarchical global routing ⋮ Neural and delay based heuristics for the Steiner problem in networks ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ Motif statistics. ⋮ Improved methods for approximating node weighted Steiner trees and connected dominating sets. ⋮ The Steiner problem in distributed computing systems

Cites Work

• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A fast algorithm for Steiner trees
• On Steiner Minimal Trees with Rectilinear Distance
• Rectilinear steiner trees: Efficient special-case algorithms
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• The steiner problem in graphs

This page was built for publication: The computation of nearly minimal Steiner trees in graphs