• search hit 2 of 2
Back to Result List

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

Author:Horst W. Hamacher, Anika Kinscherff
URN (permanent link):urn:nbn:de:hbz:386-kluedo-46674
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (163)
Document Type:Working Paper
Language of publication:English
Publication Date:2017/06/13
Year of Publication:2017
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2017/06/14
Number of page:21
Faculties / Organisational entities: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)