Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners

MaRDI QIDQ4607979zbMATH OpenFDO

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, http://dl.acm.org/citation.cfm?id=3175396

Mathematics Subject Classification ID

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)

Recommendations

• scientific article; zbMATH DE number 7053319
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Approximating the girth
• Approximating the girth
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

Cited in

(10)

• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Improved sourcewise roundtrip spanners with constant stretch
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• A fast algorithm for source-wise round-trip spanners
• Roundtrip spanners and roundtrip routing in directed graphs
• scientific article; zbMATH DE number 7561542 (Why is no real title available?)
• 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
• Deterministic improved round-trip spanners
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs

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)