An Efficient Approximation Algorithm for the Steiner Tree Problem

DOI10.1007/978-3-030-41672-0_15zbMath1440.68331arXiv1709.03867OpenAlexW3013754835MaRDI QIDQ3297834

Chi-Yeh Chen, Sun-Yuan Hsieh

Publication date: 20 July 2020

Published in: Complexity and Approximation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.03867

zbMATH Keywords

network designapproximation algorithmsSteiner treesgraph Steiner problem

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• The full Steiner tree problem
• The Steiner tree problem on graphs: inapproximability results
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• New approximation algorithms for the Steiner tree problems
• On the terminal Steiner tree problem.
• The internal Steiner tree problem: Hardness and approximations
• An 11/6-approximation algorithm for the network Steiner problem
• Algorithms for terminal Steiner trees
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• On the Full and Bottleneck Full Steiner Tree Problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• Polylogarithmic inapproximability
• Improved Approximations for the Steiner Tree Problem
• Thek-Steiner Ratio in Graphs
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• RNC-approximation algorithms for the steiner problem
• Tighter Bounds for Graph Steiner Tree Approximation
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• On the Internal Steiner Tree Problem
• New Reduction Techniques for the Group Steiner Tree Problem

This page was built for publication: An Efficient Approximation Algorithm for the Steiner Tree Problem