Faster approximation algorithms for the rectilinear Steiner tree problem

DOI10.1007/PL00009310MaRDI QIDQ1361816zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Steiner tree problem

Mathematics Subject Classification ID

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

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

Cited in

(11)

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

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)