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

DOI10.1007/BFB0015438zbMATH Open1512.68203MaRDI QIDQ6487979FDOQ6487979

Authors: Siu-Wing Cheng, C. K. Tang 

Publication date: 21 March 2023

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

Mathematics Subject Classification ID

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

Cites Work

• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Convexity and the Steiner tree problem
• Title not available (Why is that?)
• Faster exact algorithms for steiner trees in planar networks
• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• Title not available (Why is that?)

Cited In (4)

• An algorithm for exact rectilinear Steiner trees for switchbox with obstacles
• A rectilinear steiner minimal tree algorithm for convex point sets
• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon

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)