Tighter Bounds for Graph Steiner Tree Approximation

DOI10.1137/S0895480101393155zbMath1082.05088OpenAlexW2039298646MaRDI QIDQ5317602

Gabriel Robins, Alexander Z. Zelikovsky

Publication date: 16 September 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480101393155

zbMATH Keywords

approximation algorithms

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (56)

$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Models of greedy algorithms for graph problems ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ CONSTRAINED RELAY NODE DEPLOYMENT FOR UNDERWATER ACOUSTIC WIRELESS SENSOR NETWORKS ⋮ 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 ⋮ A robust and scalable algorithm for the Steiner problem in graphs ⋮ The Influence of Preprocessing on Steiner Tree Approximations ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ Approximating activation edge-cover and facility location problems ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound ⋮ On the complexity of the cable-trench problem ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ Improved approximation algorithms for directed Steiner forest ⋮ On the Price of Stability of Undirected Multicast Games ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Euclidean prize-collecting Steiner forest ⋮ Unnamed Item ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Constrained surface-level gateway placement for underwater acoustic wireless sensor networks ⋮ Combination algorithms for Steiner tree variants ⋮ Approximations for node-weighted Steiner tree in unit disk graphs ⋮ New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ Strategyproof auction mechanisms for network procurement ⋮ Strong Steiner Tree Approximations in Practice ⋮ Bounding the payment of approximate truthful mechanisms ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ Algorithms for terminal Steiner trees ⋮ A simpler and better derandomization of an approximation algorithm for single source rent-or-buy ⋮ On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ A partition-based relaxation for Steiner trees ⋮ Unnamed Item ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Travelling on graphs with small highway dimension ⋮ Multi-level Steiner Trees ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ On the Clustered Steiner Tree Problem ⋮ Multi-Level Steiner Trees. ⋮ On the clustered Steiner tree problem ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications

This page was built for publication: Tighter Bounds for Graph Steiner Tree Approximation