Approximation algorithms for spanner problems and directed Steiner forest

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

zbMATH Keywords

approximation algorithmdirected graphdirected 3-spanners with unit edge lengthsdirected Steiner forest problemsparsest spanner

Mathematics Subject Classification ID

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