An Integer Network Flow Problem with Bridge Capacities

  • In this paper a modified version of dynamic network ows is discussed. Whereas dynamic network flows are widely analyzed already, we consider a dynamic flow problem with aggregate arc capacities called Bridge Problem which was introduced by Melkonian [Mel07]. We extend his research to integer flows and show that this problem is strongly NP-hard. For practical relevance we also introduce and analyze the hybrid bridge problem, i.e. with underlying networks whose arc capacity can limit aggregate flow (bridge problem) or the flow entering an arc at each time (general dynamic flow). For this kind of problem we present efficient procedures for special cases that run in polynomial time. Moreover, we present a heuristic for general hybrid graphs with restriction on the number of bridge arcs. Computational experiments show that the heuristic works well, both on random graphs and on graphs modeling also on realistic scenarios.

Download full text files

Export metadata

Metadaten
Author:Horst W. Hamacher, Anika Kinscherff
URN:urn:nbn:de:hbz:386-kluedo-46674
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (163)
Document Type:Working Paper
Language of publication:English
Date of Publication (online):2017/06/13
Year of first Publication:2017
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2017/06/14
Page Number:21
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)