{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihg57rht4m74rwd5vdvw4c4lmfxnqwr4ik64e6owpjahg5mrwa3uy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkz5ff2mgd72"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.00277v1",
  "publishedAt": "2026-05-04T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Shuchi Chawla",
    "Kristin Sheridan"
  ],
  "textContent": "**Authors:** Shuchi Chawla, Kristin Sheridan\n\nWe 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.",
  "title": "Brief announcement: A special case of maximum flow over time with network changes"
}