2 papers
cs.DS2022
Worst-Case to Expander-Case Reductions
Amir Abboud, Nathan Wallheimer
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful ham…
cs.DS2022
Improved Compression of the Okamura-Seymour Metric
Shay Mozes, Nathan Wallheimer, Oren Weimann
Let be an undirected unweighted planar graph. Consider a vector storing the distances from an arbitrary vertex to all vertices of…