Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
zbMATH Open1403.68173arXiv1611.00721MaRDI QIDQ4607979FDOQ4607979
Authors: Jakub W. Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams 
Publication date: 15 March 2018
Full work available at URL: https://arxiv.org/abs/1611.00721
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Paths and cycles (05C38)
Cited In (10)
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- Title not available (Why is that?)
- On the VC-dimension of unique round-trip shortest path systems
- Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
- Improved sourcewise roundtrip spanners with constant stretch
- Deterministic improved round-trip spanners
- A fast algorithm for source-wise round-trip spanners
- Roundtrip spanners and roundtrip routing in directed graphs
- Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
This page was built for publication: Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607979)
