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

combined algorithmSteiner minimum treeSteiner pointSteiner treeSteiner tree problem

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

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

Cited in

(25)

• Fast heuristic algorithms for rectilinear Steiner trees
• The role of Steiner hulls in the solution to Steiner tree problems
• Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Faster approximation algorithms for the rectilinear Steiner tree problem
• 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
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• Two-level rectilinear Steiner trees
• The number of tree stars is \(O^{*}(1.357^k)\)
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• The number of tree stars is O*(1.357k)
• scientific article; zbMATH DE number 4041289 (Why is no real title available?)
• scientific article; zbMATH DE number 1286270 (Why is no real title available?)
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees
• scientific article; zbMATH DE number 1163724 (Why is no real title available?)
• Thirty‐five‐point rectilinear steiner minimal trees in a day
• scientific article; zbMATH DE number 742891 (Why is no real title available?)
• Reductions for the rectilinear steiner tree problem
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Logic Programming

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)