An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time

Proceedings of the 58th Annual ACM Symposium on Theory of Computing 2026 Open access

Read full text
Authors: Monika Rauch Henzinger, Robin Münk, Harald Räcke
DOI: 10.1145/3798129.3800851
Cited by: 1
References: 28

Abstract

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 flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Graph Theory and Algorithms Data Management and Algorithms

Publication details

Journal / source
Proceedings of the 58th Annual ACM Symposium on Theory of Computing
Publisher
ACM
Pages
1417–1428
Publication date
9 June 2026
Language
EN