AN 0 (N log N) HEURISTIC ALGORITHM FOR THE RECTILINEAR STEINER MINIMAL TREE PROBLEM
- 1 January 1980
- journal article
- Published by Taylor & Francis in Engineering Optimization
- Vol. 4 (4) , 179-192
- https://doi.org/10.1080/03052158008902421
Abstract
This paper presents an 0 (n log n) heuristic algorithm for the Rectilinear Steiner Minimal Tree (RSMT) problem. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the L1 Delaunay triangulation, then constructs the Steiner minimal tree according to the properties of the Voronoi diagram and the Minimum Spanning Tree (MST) of the point set. The algorithm was implemented in FORTRAN-IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the 0 (n log n) algorithms with 0 (n4) algorithms indicates that the 0 (n log n) algorithm achieves equally good reductions over the MST although the 0 (n4) algorithms actually examine more potential Steiner points and RSMT configurationsKeywords
This publication has 16 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- An O(n log n) algorithm for suboptimal rectilinear Steiner treesIEEE Transactions on Circuits and Systems, 1979
- The Complexity of Computing Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1977
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- Rectilinear steiner trees: Efficient special-case algorithmsNetworks, 1977
- Finding Minimum Spanning TreesSIAM Journal on Computing, 1976
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976
- Graph Theory with ApplicationsPublished by Springer Nature ,1976
- A note on Fermat's problemMathematical Programming, 1973
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966