An improved algorithm for the Steiner tree problem with bounded edge-length

DOI10.1016/J.JCSS.2021.07.003MaRDI QIDQ2237889zbMATH OpenOpenAlexFDO

Authors C. Y. Chen, Sun-Yuan Hsieh

Publication date 28 October 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2021.07.003

zbMATH Keywords

randomized algorithmsapproximation algorithmsgreedy algorithmsnetwork designSteiner trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Tighter Bounds for Graph Steiner Tree Approximation
• scientific article; zbMATH DE number 1445376
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• Improved Approximations for the Steiner Tree Problem

Cites work

• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305435 (Why is no real title available?)
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• An 11/6-approximation algorithm for the network Steiner problem
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Improved Approximations for the Steiner Tree Problem
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• New approximation algorithms for the Steiner tree problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• RNC-approximation algorithms for the steiner problem
• Steiner tree approximation via iterative randomized rounding
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results
• The computation of nearly minimal Steiner trees in graphs
• The internal Steiner tree problem: Hardness and approximations
• Thek-Steiner Ratio in Graphs
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(5)

• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• scientific article; zbMATH DE number 6381651 (Why is no real title available?)
• An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2
• Improved Steiner tree algorithms for bounded treewidth
• Reliability assessment of the divide-and-swap cube in terms of generalized connectivity

This page was built for publication: An improved algorithm for the Steiner tree problem with bounded edge-length

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