direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints

Stable Flows over Time
Zitatschlüssel Report-023-2012
Autor Cseh, Ágnes and Matuschke, Jannik and Skutella, Martin
Jahr 2012
Nummer 023
Zusammenfassung 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 infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag