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

DOI10.1016/0020-0190(88)90225-6zbMATH Open0662.68039OpenAlexW2087598714MaRDI QIDQ1114397FDOQ1114397

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Steiner problem in networks: A survey
• Routing to Multiple Destinations in Computer Networks
• A fast algorithm for Steiner trees
• Title not available (Why is that?)
• On finding steiner vertices
• 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
• Title not available (Why is that?)
• 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)