Using expanders for dynamic graph algorithms: a survey of tools by Thatchaphol Saranurak

STOC'22 Workshop
Dynamic Algorithms: Recent Advances and Applications

Abstract:
In the last few years, expanders have been used as a main tool in a large number of dynamic graph algorithms. I will explain why expanders can be useful for dynamic graph problems and how the recent algorithms can exploit expanders even if the input graph is not an expander. We will see all expander-related tools (known to me) and how these tools are being used in the literature.