A fast algorithm for computing optimal rectilinear Steiner trees for extremal point sets

DOI10.1007/BFB0015438MaRDI QIDQ6487979zbMATH OpenFDO

Authors Siu-Wing Cheng, C. K. Tang

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015438

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• scientific article; zbMATH DE number 3972878
• A rectilinear steiner minimal tree algorithm for convex point sets
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees
• Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

Cites work

• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• Convexity and the Steiner tree problem
• Faster exact algorithms for steiner trees in planar networks
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 1555952 (Why is no real title available?)
• Send-and-Split Method for Minimum-Concave-Cost Network Flows

Cited in

(5)

• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• An algorithm for exact rectilinear Steiner trees for switchbox with obstacles
• A rectilinear steiner minimal tree algorithm for convex point sets

This page was built for publication: A fast algorithm for computing optimal rectilinear Steiner trees for extremal point sets

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