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