Academic Journals Database
Disseminating quality controlled scientific knowledge

Stable Flows over Time

ADD TO MY LIST
 
Author(s): Ágnes Cseh | Jannik Matuschke | Martin Skutella

Journal: Algorithms
ISSN 1999-4893

Volume: 6;
Issue: 3;
Start page: 532;
Date: 2013;
Original page

Keywords: stable matchings | stable flows | flows over time

ABSTRACT
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.
RPA Switzerland

RPA Switzerland

Robotic process automation

    

Tango Jona
Tangokurs Rapperswil-Jona