Graph Algorithms and Batched Processing

September 16, 2019, 2:00 PM - 2:40 PM


Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

Richard Peng, Georgia Institute of Technology

Computing and maintaining large graphs are increasingly important problems in data mining, machine learning, and security. This talk will use progress on two well-studied problems in static and dynamic graph algorithms, net-work flows and dynamic matchings, to discuss a methodology for designing faster algorithm for large graphs motivated by long-standing open problems in data structures.

I will start by describing how studies of network flows led to a focus on residual networks, which in turn motivated faster algorithms as well as more general notions of preconditioning. I will then discuss a similar phenomenon in dynamic graphs, where the current best algorithms for maintaining large matchings utilize kernels built from dual vertex covers.