UNIVERSITÄTSBIBLIOTHEK

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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Horst W. Hamacher, Anika Kinscherff
URN (Permalink):urn:nbn:de:hbz:386-kluedo-46674
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (163)
Dokumentart:Arbeitspapier
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):13.06.2017
Jahr der Veröffentlichung:2017
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):14.06.2017
Seitenzahl:21
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)