Solving rectilinear Steiner tree problems exactly in theory and practice

DOI10.1007/3-540-63397-9_14MaRDI QIDQ826086zbMATH OpenOpenAlexFDO

Authors Ulrich Fößmeier, Michael Kaufmann

Publication date 20 December 2021

Full work available at URL https://doi.org/10.1007/3-540-63397-9_14

zbMATH Keywords

Steiner tree problemSteiner treeSteiner minimum treeSteiner pointcombined algorithm

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)

Recommendations

• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• scientific article; zbMATH DE number 1163724
• Publication:4945796
• Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
• Thirty‐five‐point rectilinear steiner minimal trees in a day

Cited in

(19)

• scientific article; zbMATH DE number 742891 (Why is no real title available?)
• The number of tree stars is O*(1.357k)
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• Logic Programming
• Fast heuristic algorithms for rectilinear Steiner trees
• The number of tree stars is \(O^{*}(1.357^k)\)
• Two-level rectilinear Steiner trees
• scientific article; zbMATH DE number 4041289 (Why is no real title available?)
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Reductions for the rectilinear steiner tree problem
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• The role of Steiner hulls in the solution to Steiner tree problems
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study

This page was built for publication: Solving rectilinear Steiner tree problems exactly in theory and practice

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