3 papers
cs.DS2026
Expander Hierarchies for Normalized Cuts on Graphs
Kathrin Hanauer, Monika Henzinger, Robin Münk +2
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their…
cs.DS2025
An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
Monika Henzinger, Robin Münk, Harald Räcke
A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flo…
cs.DS2025
Efficient Contractions of Dynamic Graphs -- with Applications
Monika Henzinger, Evangelos Kosinas, Robin Münk +1
A non-trivial minimum cut (NMC) sparsifier is a multigraph that preserves all non-trivial minimum cuts of a given undirected graph . We introduce a flexible data struc…