Constant Girth Approximation for Directed Graphs in Subquadratic Time

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.