Finding sparser directed spanners

DOI10.4230/LIPICS.FSTTCS.2010.424MaRDI QIDQ2908874zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Sofya Raskhodnikova, Ge Ruan

Publication date 29 August 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_9b2c.html

zbMATH Keywords

approximation algorithmsdirected graphsspanners

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Improved approximation for the directed spanner problem
• Transitive-closure spanners
• Approximation algorithms for spanner problems and directed Steiner forest
• Transitive-closure spanners
• Generating sparse 2—spanners

Cited in

(13)

• Approximation algorithms for spanner problems and directed Steiner forest
• Sparsification lower bound for linear spanners in directed graphs
• Parameterized complexity of directed spanner problems
• Improved approximation for the directed spanner problem
• Relaxed Spanners for Directed Disk Graphs
• Strongly connected spanning subgraph for almost symmetric networks
• Transitive-closure spanners
• Transitive-closure spanners
• Transitive-closure spanners: a survey
• Distributed spanner approximation
• Directed spanners via flow-based linear programs
• Parameterized Complexity of Directed Spanner Problems.
• Roundtrip spanners with (2k-1) stretch

This page was built for publication: Finding sparser directed spanners

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