Approximation algorithms for spanner problems and directed Steiner forest

DOI10.1016/J.IC.2012.10.007MaRDI QIDQ1951575zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev

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 3-spanners with unit edge lengthsdirected graphdirected Steiner forest problemsparsest spanner

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Improved approximation for the directed spanner problem
• Approximating spanners and directed Steiner forest. Upper and lower bounds
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Directed spanners via flow-based linear programs
• Finding sparser directed spanners

Cited in

(31)

• Graph spanners: a tutorial review
• Lasserre integrality gaps for graph spanners and related problems
• Roots of bivariate polynomial systems via determinantal representations
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Finding sparser directed spanners
• Improved approximation for the directed spanner problem
• On directed Steiner trees with multiple roots
• Improved approximation algorithms for directed Steiner forest
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Online Buy-at-Bulk Network Design
• Improved approximating algorithms for directed Steiner forest
• Approximating approximate distance oracles
• Approximating spanners and directed Steiner forest. Upper and lower bounds
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Distributed spanner approximation
• Parameterized approximation algorithms for bidirected Steiner network problems
• How to Secure Matchings Against Edge Failures
• How to Secure Matchings against Edge Failures
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Directed spanners via flow-based linear programs
• Approximating the norms of graph spanners
• Online Directed Spanners and Steiner Forests.
• An ETH-tight algorithm for bidirected Steiner connectivity
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
• On the bidirected cut relaxation for Steiner forest
• Spanner approximations in practice
• The strongish planted clique hypothesis and its consequences
• Approximation algorithms for directed weighted spanners
• Exact minimum weight spanners via column generation
• Directed buy-at-bulk spanners

This page was built for publication: Approximation algorithms for spanner problems and directed Steiner forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1951575)