DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2026.23

Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes

Authors: Shuchi Chawla and Kristin Sheridan

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

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 over time. We assume that the capacity of every edge in the network is a piecewise constant function and parameterize the running time of our algorithm by the total number of pieces in the capacity functions across all edges, denoted μ. The key technical component in our approach is a condensed version of a Time Expanded Network (that we call a cTEN) whose classical max flow value is the same as the max flow over time on the original network. We show that a graph with n nodes, m edges, and μ capacity changes, admits a cTEN with O(n²μ) nodes and O(μ mn) edges. This implies that the problem can be solved in O(μ²n³m) time using the combinatorial max flow algorithm of Orlin [Orlin, 2013], or in O(μ^(1+o(1)) (nm)^(1+o(1)) log (nUT)) time using the algorithm of Chen et al. [Chen et al., 2022], where U is the maximum capacity of any edge and T is the time horizon. When μ >> m,n, this is faster than previously known algorithms for this problem.

Cite as

Shuchi Chawla and Kristin Sheridan. Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 23:1-23:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.SAND.2026.23,
  author =	{Chawla, Shuchi and Sheridan, Kristin},
  title =	{{Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{23:1--23:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.23},
  URN =		{urn:nbn:de:0030-drops-262578},
  doi =		{10.4230/LIPIcs.SAND.2026.23},
  annote =	{Keywords: maximum flow, dynamic flows, flows over time}
}

Search Results

Documents authored by Sheridan, Kristin

Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes

Abstract

Cite as

Thanks for your feedback!

Could not send message