direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Abstract flows over time: A first step towards solving dynamic packing problems
Zitatschlüssel Report-001-2012
Autor Kappmeier, Jan-Philipp W. and Matuschke, Jannik and Peis, Britta
Jahr 2012
Nummer 001
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Abstract flows generalize classical network flows by replacing the under- lying network by an abstract system of "paths" fulfilling a simple switching property: Whenever two paths P and Q intersect, there must be another path that is contained in the beginning of P and the end of Q. Flows over time generalize classical network flows by introducing a notion of time. Travelling times specify how long flow takes to traverse an edge and at each point in time the capacity of all edges must be respected. For both versions, max flow/min cut theorems have been established and efficient algorithms for computing maximum flows are known. We show that those results still hold when combining the two concepts. In particular, we show that a maximum abstract flow over time can be obtained by solving a weighted abstract flow problem and constructing a temporally repeated flow from its solution. In the course of the proof, we also show that the relatively modest switching property of abstract networks already captures many essential properties of classical networks.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag