Conditionally optimal approximation algorithms for the girth of a directed graph

DOI10.4230/LIPICS.ICALP.2020.35MaRDI QIDQ6842541zbMATH OpenFDO

Authors M. Dalirrooyfard, Virginia Vassilevska Williams

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.35

zbMATH Keywords

approximation algorithmsgraph algorithmsgirthshortest cyclefine-grained complexityroundtrip spanner

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 437547 (Why is no real title available?)
• scientific article; zbMATH DE number 7561506 (Why is no real title available?)
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Color-coding
• Cycles of even length in graphs
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• Multiplying matrices faster than coppersmith-winograd
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Powers of tensors and fast matrix multiplication
• Subcubic equivalences between path, matrix and triangle problems
• Tight hardness for shortest cycles and paths in sparse graphs

Cited in

(1)

• Fully dynamic algorithms for minimum weight cycle and related problems

This page was built for publication: Conditionally optimal approximation algorithms for the girth of a directed graph

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