Constant Girth Approximation for Directed Graphs in Subquadratic Time

Explore a cutting-edge algorithm for approximating the girth of directed graphs in subquadratic time through this 22-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into approximation algorithms for girth, roundtrip distance, and spanners in directed graphs. Examine directed graph primitives that match undirected graphs, and learn about ball growing techniques for girth approximation and spanners. Discover accelerated ball growing with overlaps, random sampling, and distance tests. Analyze the combination of two algorithms and discuss future directions and problems in this field of graph theory and algorithm design.

Intro
Talk Outline
Approximation Algorithms for the Girth
Roundtrip Distance and Spanners
Directed Graph Primitives Matching Undirected Graphs
Ball Growing for Girth Approximation and Spanners
Accelerated Ball Growing with Overlaps
Random Sampling and Distance Tests
Algorithm 3: Combination of Algo 1 and 2
Future Directions / Problems