Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study

DOI10.1016/0166-218X(93)90010-LzbMath0784.90043MaRDI QIDQ1309809

Celso Carneiro Ribeiro, Cid Carvalho De Souza

Publication date: 21 March 1994

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

zbMATH Keywords

approximate algorithmsminimum rectilinear Steiner tree problemtwo- point-connection strategy

Mathematics Subject Classification ID

Trees (05C05) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem
• Two probabilistic results on rectilinear Steiner trees
• Fast heuristic algorithms for rectilinear Steiner trees
• Path-distance heuristic for the Steiner problem in undirected networks
• A heuristic for Euclidean and rectilinear Steiner problems
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• Steiner problem in networks: A survey
• On Steiner Minimal Trees with Rectilinear Distance
• Use of Steiner's problem in suboptimal routing in rectilinear metric
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On Steiner’s Problem with Rectilinear Distance