Worst-case performance of Rayward-Smith's Steiner tree heuristic

DOI10.1016/0020-0190(88)90225-6MaRDI QIDQ1114397zbMATH OpenOpenAlexFDO

Authors Bernard M. Waxman, Makoto Imase

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1771&context=cse_research

zbMATH Keywords

approximation algorithmNP-completeoptimalSteiner treeworst-case

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

We prove that the worst-case performance of the Steiner tree approximation algorithm by \textit{V. J. Rayward-Smith} (RS) [Int. J. Math. Educ. Sci. Technol. 14, 15-23 (1983; Zbl 0512.05024)] is within two times optimal and that two is the best bound in the sense that there are instances for which RS will do worse than any value less than two.

Recommendations

• scientific article; zbMATH DE number 32742
• scientific article; zbMATH DE number 139919
• Publication:4934235
• scientific article; zbMATH DE number 125486
• A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem

Cites work

• A fast algorithm for Steiner trees
• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• On finding steiner vertices
• Routing to Multiple Destinations in Computer Networks
• Steiner problem in networks: A survey
• The computation of nearly minimal Steiner trees in graphs

Cited in

(10)

• The Steiner problem with edge lengths 1 and 2
• Branch-and-bound as a higher-order function
• Path-distance heuristic for the Steiner problem in undirected networks
• Heuristics for the Steiner problem in graphs
• Steiner's problem in graphs: Heuristic methods
• Worst-case performance of some heuristics for Steiner's problem in directed graphs
• scientific article; zbMATH DE number 32742 (Why is no real title available?)
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Models of greedy algorithms for graph problems
• A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem

This page was built for publication: Worst-case performance of Rayward-Smith's Steiner tree heuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114397)