Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Constant Girth Approximation for Directed Graphs in Subquadratic Time

Association for Computing Machinery (ACM) via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

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)

Reviews

Start your review of Constant Girth Approximation for Directed Graphs in Subquadratic Time

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.