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

DOI10.1109/TCS.1979.1084551MaRDI QIDQ4174637zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(11)

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

This page was built for publication: An O(n log n) algorithm for suboptimal rectilinear Steiner trees

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