A heuristic for Euclidean and rectilinear Steiner problems

DOI10.1016/0377-2217(92)90214-TzbMath0757.90080OpenAlexW2011065039MaRDI QIDQ1194744

John E. Beasley

Publication date: 6 October 1992

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(92)90214-t

zbMATH Keywords

heuristicminimal spanning treeconnected subgraphsrectilinear Steiner problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (11)

On the Steiner ratio in 3-space ⋮ Short trees in polygons ⋮ A heuristic for the Steiner problem in graphs ⋮ The Steiner tree problem in orientation metrics ⋮ An exact branch and bound algorithm for the Steiner Problem in Graphs ⋮ A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\) ⋮ Viral systems: A new bio-inspired optimisation approach ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study ⋮ Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs ⋮ A neural network for the Steiner minimal tree problem

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A linear time algorithm for full Steiner trees
• Exact computation of Steiner minimal trees in the plane
• Fast heuristic algorithms for rectilinear Steiner trees
• An algorithm for the steiner problem in the euclidean plane
• An SST-based algorithm for the steiner problem in graphs
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• Use of Steiner's problem in suboptimal routing in rectilinear metric
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees
• The Generation of Minimal Trees with a Steiner Topology
• Steiner tree problems

This page was built for publication: A heuristic for Euclidean and rectilinear Steiner problems