Till innehåll på sidan

Thatchaphol Saranurak: Dynamic (Minimum) Spanning Forest with Worst-case Update Time

Tid: Må 2017-04-24 kl 12.00

Plats: Room 4523, Lindstedtsvägen 5, KTH CSC

Medverkande: Thatchaphol Saranurak, (TCS group - KTH)

Exportera till kalender

Abstract
We will discuss recent algorithms for dynamically maintaining a (minimum) spanning forest of a graph undergoing edge insertions and deletions. This problem played a central role in the study of dynamic graph algorithms.

We provide the "first polynomial improvement" over the long-standing O(sqrt{n}) bound of [Frederickson STOC’83, Eppstein et. al FOCS’92] for dynamic spanning forest problem.  Independently, Wulff-Nilsen shows the first polynomial improvement for dynamic minimum spanning forest problems. Both works will be presented in STOC'17.

The new crucial techniques are about expanders: 1) an algorithm for decomposing a graph into a collection of expanders in near-linear time, and 2) an algorithm for "repairing" the expansion property of an expander after deleting some edges of it. These techniques can be of independent interest.