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

DOI10.1016/J.JCSS.2021.07.003zbMATH Open1472.68111OpenAlexW3186055442MaRDI QIDQ2237889FDOQ2237889

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

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

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)

Cites Work

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

Cited In (5)

• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• Title not available (Why is that?)
• 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)