2 papers
cs.DS2025
Multiplicative Spanners in Minor-Free Graphs
Greg Bodwin, Gary Hoppenworth, Zihan Tan
In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $…
cs.DS2024
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this p…