On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results

DOI10.1007/S004539910005MaRDI QIDQ1969944zbMATH OpenOpenAlexFDO

Authors Michael Kaufmann, Ulrich Fößmeier

Publication date 12 December 2000

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsdynamic programmingRectilinear Steiner trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Review text

The rectilinear Steiner tree problem asks for a shortest tree connecting \(n\) given points in the plane with rectilinear distance. The authors present a dynamic programming approach to this problem with worst-case time bound of \(O(n^2 \cdot 2.38^n)\), and for random instances they prove a running time of \(\alpha^n\) with constant \(\alpha<2\).

Recommendations

• Solving rectilinear Steiner tree problems exactly in theory and practice
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees
• Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
• A practical algorithm for the minimum rectilinear Steiner tree
• Thirty‐five‐point rectilinear steiner minimal trees in a day

Cited in

(25)

• Two probabilistic results on rectilinear Steiner trees
• The rectilinear class Steiner tree problem for intervals on two parallel lines
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology
• Exact solutions for the Steiner path cover problem on special graph classes
• The number of tree stars is \(O^{*}(1.357^k)\)
• Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees
• Bounding the expected number of rectilinear full Steiner trees
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• The number of tree stars is O*(1.357k)
• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• scientific article; zbMATH DE number 1286271 (Why is no real title available?)
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• scientific article; zbMATH DE number 1086912 (Why is no real title available?)
• scientific article; zbMATH DE number 1163707 (Why is no real title available?)
• Subclass of the Steiner problems on a plane with rectilinear metric
• scientific article; zbMATH DE number 742891 (Why is no real title available?)
• scientific article; zbMATH DE number 1424544 (Why is no real title available?)
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Definition and algorithms for reliable Steiner tree problem
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Solving rectilinear Steiner tree problems exactly in theory and practice
• Comments on Bern's probabilistic results on rectilinear Steiner trees

This page was built for publication: On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results

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