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)

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)