An O(n log n) algorithm for suboptimal rectilinear Steiner trees
From MaRDI portal
Publication:4174637
DOI10.1109/TCS.1979.1084551zbMath0392.94023OpenAlexW2082293426MaRDI QIDQ4174637
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
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