Local search for the Steiner tree problem in the Euclidean plane

DOI10.1016/S0377-2217(99)00131-9zbMath0933.90065OpenAlexW2088172021MaRDI QIDQ1806730

Martin Zachariasen

Publication date: 8 November 1999

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00131-9

zbMATH Keywords

heuristicslocal searchSteiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Maximising the worth of nascent networks, Short trees in polygons, LS(graph): a constraint-based local search for constraint optimization on trees and paths, Heuristics for automated knowledge source integration and service composition, A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\)

Uses Software

• LEDA
• OR-Library
• FindSteinerTree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On better heuristics for Steiner minimum trees
• A linear time algorithm for full Steiner trees
• Steiner minimal trees for three points with one convex polygonal obstacle
• How to find Steiner minimal trees in Euclidean \(d\)-space
• A heuristic for Euclidean and rectilinear Steiner problems
• Steiner's problem in graphs: Heuristic methods
• The Steiner tree problem
• Two heuristics for the Euclidean Steiner tree problem
• A neural network for the Steiner minimal tree problem
• A data structure for dynamic trees
• Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
• On the Problem of Steiner
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• The shortest network under a given topology
• Steiner Trees for Ladders
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• Improved Approximations for the Steiner Tree Problem
• Experimental evaluation of a partitioning algorithm for the steiner tree problem in R² and R³
• Euclidean Steiner minimum trees: An improved exact algorithm
• A Dynamic Adaptive Relaxation Scheme Applied to the Euclidean Steiner Minimal Tree Problem
• An O(N²) heuristic for steiner minimal trees in E³
• Steiner Minimal Trees
• The Generation of Minimal Trees with a Steiner Topology