Solving rectilinear Steiner tree problems exactly in theory and practice

DOI10.1007/3-540-63397-9_14zbMATH Open1477.68226OpenAlexW1693948900MaRDI QIDQ826086FDOQ826086

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

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

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)

Cited In (19)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)