Faster approximation algorithms for the rectilinear Steiner tree problem

DOI10.1007/PL00009310zbMATH Open0872.68140OpenAlexW2028766782MaRDI QIDQ1361816FDOQ1361816

Authors: Ulrich Fößmeier, Michael Kaufmann, Alex Zelikovsky 

Publication date: 28 July 1997

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

Recommendations

• A practical algorithm for the minimum rectilinear Steiner tree
• scientific article; zbMATH DE number 742979
• Improved Approximations for the Steiner Tree Problem
• Solving rectilinear Steiner tree problems exactly in theory and practice
• New approximation algorithms for the Steiner tree problems

zbMATH Keywords

Steiner tree problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cited In (11)

• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• The number of tree stars is \(O^{*}(1.357^k)\)
• Two-level rectilinear Steiner trees
• A note on A faster approximation algorithm for the Steiner problem in graphs
• Title not available (Why is that?)
• Reductions for the rectilinear steiner tree problem
• A practical algorithm for the minimum rectilinear Steiner tree
• Bounding the expected number of rectilinear full Steiner trees
• Improved Approximations for the Steiner Tree Problem
• Title not available (Why is that?)

This page was built for publication: Faster approximation algorithms for the rectilinear Steiner tree problem

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