Approximation algorithms for spanner problems and directed Steiner forest
From MaRDI portal
Publication:1951575
DOI10.1016/j.ic.2012.10.007zbMath1267.68317OpenAlexW1986144992MaRDI QIDQ1951575
Arnab Bhattacharyya, Grigory Yaroslavtsev, Konstantin Makarychev, Sofya Raskhodnikova, Piotr Berman
Publication date: 6 June 2013
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2012.10.007
approximation algorithmdirected graphdirected 3-spanners with unit edge lengthsdirected Steiner forest problemsparsest spanner
Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (16)
On Directed Steiner Trees with Multiple Roots ⋮ Online Buy-at-Bulk Network Design ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Unnamed Item ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ How to Secure Matchings against Edge Failures ⋮ Graph spanners: a tutorial review ⋮ Roots of Bivariate Polynomial Systems via Determinantal Representations ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ How to Secure Matchings Against Edge Failures ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Distributed Spanner Approximation ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Unnamed Item ⋮ Lasserre integrality gaps for graph spanners and related problems
This page was built for publication: Approximation algorithms for spanner problems and directed Steiner forest
