An O(n log n) algorithm for suboptimal rectilinear Steiner trees

DOI10.1109/TCS.1979.1084551zbMath0392.94023OpenAlexW2082293426MaRDI QIDQ4174637

Frank K. Hwang

Publication date: 1979

Published in: IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tcs.1979.1084551

zbMATH Keywords

Suboptimal Rectilinear Steiner Tree Algorithm

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory to circuits and networks (94C15) Software, source code, etc. for problems pertaining to combinatorics (05-04) Software, source code, etc. for problems pertaining to information and communication theory (94-04)

Related Items

Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, Two probabilistic results on rectilinear Steiner trees, Fast heuristic algorithms for rectilinear Steiner trees, The Steiner tree problem in orientation metrics, A probably fast, provably optimal algorithm for rectilinear Steiner trees, A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem, An integrated approach to routing and via minimization, A heuristic for Euclidean and rectilinear Steiner problems, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, The computation of nearly minimal Steiner trees in graphs, Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study