A heuristic for Euclidean and rectilinear Steiner problems

DOI10.1016/0377-2217(92)90214-TMaRDI QIDQ1194744zbMATH OpenOpenAlexFDO

Authors J. 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

connected subgraphsheuristicminimal spanning treerectilinear Steiner problems

Mathematics Subject Classification ID

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

Recommendations

• Two heuristics for the Euclidean Steiner tree problem
• Steiner's problem in graphs: Heuristic methods
• Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study
• Publication:3028682
• Fast heuristic algorithms for rectilinear Steiner trees

Cites work

• A linear time algorithm for full Steiner trees
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• An algorithm for the steiner problem in the euclidean plane
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• An SST-based algorithm for the steiner problem in graphs
• Exact computation of Steiner minimal trees in the plane
• Fast heuristic algorithms for rectilinear Steiner trees
• scientific article; zbMATH DE number 3695224 (Why is no real title available?)
• scientific article; zbMATH DE number 3735154 (Why is no real title available?)
• scientific article; zbMATH DE number 3735816 (Why is no real title available?)
• scientific article; zbMATH DE number 3557226 (Why is no real title available?)
• scientific article; zbMATH DE number 3388861 (Why is no real title available?)
• scientific article; zbMATH DE number 3401212 (Why is no real title available?)
• On Steiner’s Problem with Rectilinear Distance
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Shortest trees and Steiner trees with rectilinear distances
• Steiner Minimal Trees
• Steiner tree problems
• The Complexity of Computing Steiner Minimal Trees
• The Generation of Minimal Trees with a Steiner Topology
• The Rectilinear Steiner Tree Problem is NP-Complete
• Use of Steiner's problem in suboptimal routing in rectilinear metric

Cited in

(22)

• Fast heuristic algorithms for rectilinear Steiner trees
• Two heuristics for the Euclidean Steiner tree problem
• A fast and simple Steiner routing heuristic
• 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
• On the Steiner ratio in 3-space
• Short trees in polygons
• The Steiner tree problem in orientation metrics
• Local search for the Steiner tree problem in the Euclidean plane
• A heuristic for the Steiner problem in graphs
• Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
• Viral systems: A new bio-inspired optimisation approach
• Local optimization in the Steiner problem on the Euclidean plane
• Dual heuristics on the exact solution of large Steiner problems
• New heuristics for the Euclidean Steiner problem in \(\mathbb{R}^n\)
• scientific article; zbMATH DE number 4016557 (Why is no real title available?)
• On finding steiner vertices
• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• A Geometric Heuristic for Rectilinear Crossing Minimization
• 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\)

Describes a project that uses

Uses Software

• OR-Library

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194744)