Heuristics for the Steiner problem in graphs

DOI10.1016/0166-218X(92)90151-YzbMath0768.68171MaRDI QIDQ1199447

Ján Plesník

Publication date: 16 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

worst-case performance; average distance heuristic; contraction heuristic; minimum cost tree; path heuristic; spanning tree heuristic; Steiner problem in graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

Related Items

Neural and delay based heuristics for the Steiner problem in networks, Generalized spanning trees

Cites Work

• Two probabilistic results on rectilinear Steiner trees
• Worst-case performance of Rayward-Smith's Steiner tree heuristic
• A fast algorithm for Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• Network decomposition for the optimization of connection structures
• On finding steiner vertices
• Steiner problem in networks: A survey
• Dynamic Steiner Tree Problem
• Une heuristique pour le problème de l'arbre de Steiner
• Routing to Multiple Destinations in Computer Networks
• The computation of nearly minimal Steiner trees in graphs
• Steiner Minimal Trees
• The steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• Steiner tree problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item