Stable flows over time

DOI10.3390/A6030532MaRDI QIDQ1736580zbMATH OpenOpenAlexFDO

Authors Ágnes Cseh, Jannik Matuschke, Martin Skutella

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a6030532

zbMATH Keywords

flows over timestable flowsstable matchings

Mathematics Subject Classification ID

Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Deterministic network models in operations research (90B10) Matching models (91B68)

Review text

Summary: In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.

Recommendations

• On stable matchings and flows
• Quickest Flows Over Time
• scientific article; zbMATH DE number 2079322

Cites work

• College Admissions and the Stability of Marriage
• Constructing maximal dynamic flows from static flows
• Faster algorithms for stable allocation problems
• Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• On stable matchings and flows
• The Stable Allocation (or Ordinal Transportation) Problem

Cited in

(5)

• Stable multicommodity flows
• Editorial: Special issue on matching under preferences
• Tame flows
• Structurally stable flows
• On stable flows and preflows

This page was built for publication: Stable flows over time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736580)