Constant Girth Approximation for Directed Graphs in Subquadratic Time
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
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
Taught by
Association for Computing Machinery (ACM)