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

optimalapproximation algorithmNP-completeSteiner treeworst-case

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• A fast algorithm for Steiner trees
• 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)

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

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)