Stable flows over time
type: Item
instance of: scholarly article
title: Stable flows over time
zbMATH Open document ID: 1461.91196
author: Ágnes Cseh
author: Jannik Matuschke
author: Martin Skutella
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
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.
Mathematics Subject Classification ID: 91B68
Mathematics Subject Classification ID: 05C21
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 7042177
zbMATH Keywords: stable matchings
zbMATH Keywords: stable flows
zbMATH Keywords: flows over time
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6030532
OpenAlex ID: W2152327218
cites work: College Admissions and the Stability of Marriage
cites work: The Stable Allocation (or Ordinal Transportation) Problem
cites work: Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
cites work: Faster algorithms for stable allocation problems
cites work: On Stable Matchings and Flows
cites work: Constructing Maximal Dynamic Flows from Static Flows
cites work: Q3292914
DOI: 10.3390/A6030532
description: scientific article; zbMATH DE number 7042177