Worst-case performance of some heuristics for Steiner's problem in directed graphs

DOI10.1016/0020-0190(93)90185-CzbMath0788.68111OpenAlexW1970669216MaRDI QIDQ1313772

Stefan Voß

Publication date: 24 February 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90185-c

zbMATH Keywords

worst-case performanceheuristic algorithmsdirected graphsSteiner treeSteiner's problem

Mathematics Subject Classification ID

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

Related Items (6)

Steiner problems on directed acyclic graphs ⋮ THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM ⋮ Worst-case performance of Wong's Steiner tree heuristic ⋮ Two variations of the minimum Steiner problem ⋮ A note on distributed multicast routing in point-to-point networks ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Worst-case performance of Rayward-Smith's Steiner tree heuristic
• Reducing the hierarchical network design problem
• A fast algorithm for Steiner trees
• Steiner's problem in graphs: Heuristic methods
• A dual ascent approach for steiner tree problems on a directed graph
• Steiner problem in networks: A survey
• Une heuristique pour le problème de l'arbre de Steiner
• A faster approximation algorithm for the Steiner problem in graphs
• Steiner tree problems

This page was built for publication: Worst-case performance of some heuristics for Steiner's problem in directed graphs