# Brief announcement: A special case of maximum flow over time with network changes

Preprint · Shuchi Chawla, Kristin Sheridan

- Archive id: arxiv:2605.00277
- Published: 2026-04-30
- arXiv: https://arxiv.org/abs/2605.00277
- Source URL: https://arxiv.org/abs/2605.00277
- PDF: https://arxiv.org/pdf/2605.00277
- Provenance: arxiv

## Abstract

We consider the problem of finding the value of a maximum flow over time in a network with uniform edge lengths where the edge capacities change at specific time instants. To solve this problem, we show how to construct a condensed version of a Time Expanded Network (cTEN) whose standard max flow value is the same as the max flow over time on the original network. In particular, for a graph with $n$ nodes, $m$ edges, and $μ$ {\\em critical times} where some edge capacity changes, we obtain a cTEN with $O(n^2μ)$ nodes and $O(μmn)$ edges. This implies that the problem can be solved in $O(μ^2n^3m)$ time using the combinatorial max flow algorithm of Orlin \[Orl13\], or in $O(μ^{(1+o(1))}(nm)^{1+o(1)}\\log (UT))$ time using the algorithm of Chen et al. \[CKL+22\], where $U$ is the maximum capacity of any edge and $T$ is the time horizon. We focus on graphs that experience many time changes across the period of interest, as in such graphs the $μ$ term dominates the runtime.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.