Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Bernhard Haeupler, D Ellis Hershkowitz, Thatchaphol Saranurak · 2023
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths have length at most h. Many well-studied algorithmic primitives—such as maximal and maximum length-constrained disjoint paths—are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives.