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) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

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

(16)

• On the VC-dimension of unique round-trip shortest path systems
• A fast algorithm for source-wise round-trip spanners
• Deterministic improved round-trip spanners
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Roundtrip spanners and roundtrip routing in directed graphs
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Faster approximation algorithms for computing shortest cycles on weighted graphs
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Improved sourcewise roundtrip spanners with constant stretch
• Conditionally optimal approximation algorithms for the girth of a directed graph
• Roundtrip spanners with (2k-1) stretch
• Negative-weight single-source shortest paths in near-linear time
• Approximation algorithms for directed weighted spanners
• Near-optimal directed low-diameter decompositions
• Directed buy-at-bulk spanners

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)