The Maximum Flow Problem for Oriented Flows

  • In several applications of network flows, additional constraints have to be considered. In this paper, we study flows, where the flow particles have an orientation. For example, cargo containers with doors only on one side and train coaches with 1st and 2nd class compartments have such an orientation. If the end position has a mandatory orientation, not every path from source to sink is feasible for routing or additional transposition maneuvers have to be made. As a result, a source-sink path may visit a certain vertex several times. We describe structural properties of optimal solutions, determine the computational complexity, and present an approach for approximating such flows.

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Stanley Schade, Martin StrehlerORCiDGND
URN:urn:nbn:de:0030-drops-65318
URL:http://drops.dagstuhl.de/opus/volltexte/2016/6531
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2016.7
ISBN:978-3-95977-021-7
Title of the source (English):16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)
Publisher:Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Place of publication:Dagstuhl, Germany
Editor: Marc Goerigk, Renato Werneck
Document Type:Conference Proceeding
Language:English
Year of publication:2016
Tag:network flow with orientation, graph expansion, approximation, container logistics, train routing
First Page:1
Last Page:13
Series ; volume number:OASIcs - OpenAccess Series in Informatics ; 54
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Algorithmische Mathematik
Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Diskrete Mathematik und Grundlagen der Informatik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.