Thatchaphol Saranurak - Graph Decomposition
What is this course about? This course studies modern graph algorithms through the lens of graph decomposition. Over the last two decades, expander decompositions and hierarchies have become some of the most powerful tools for designing fast algorithms for connectivity, cuts, flows, and
Course roadmap This course has 5 parts Basic structures: Expander Decompositions and Hierarchies Expander decompositions and hierarchies are one of the most powerful tools in designing graph algorithms in the last two decades. There are many variants of them in the literature, and it can be hard to navigate. Here, we present a unified treatment and their immediate applications. With the right notations, there are just three main objects: Expander Decomposition, Separator-Expanding Hierarchy, and Boundary-Separator-Expanding Hierarchy. The algorithms for showing their existence are very…
saved by
related reading
- CSE 599 Recent Developments in Approximation Algorithmshomes.cs.washington.edu
- A simpler proof of the KPR theorem | tcs mathtcsmath.wordpress.com
- Fernando Granha Jeronimo | Theoretical Computer Science | UIUCgranha.github.io
- CSE290A - Randomized Algorithmsusers.soe.ucsc.edu
- my projectsdan-iel-lee.vercel.app
- Cover times - spectralarxiv.org
- 1404.5236 Sum-of-Squares Proofs and the Quest toward Optimal Algorithmsarxiv.org
- Expander graph - Wikipediaen.wikipedia.org
- Sublinear expandersias.edu
- Ch12.pdfmath.uni-hamburg.de
- Visualizing Algorithmsbost.ocks.org
- annaabrandenberger.github.io