Title: Shortest path and maximum flow problems in planar flow networks with additive gains and losses
Authors: Saber Mirzaei and Assaf Kfoury
Date: March 29, 2016
Abstract:
In contrast to traditional flow networks, in additive flow networks,
to every edge e is assigned a gain factor g(e) which represents the
loss or gain of the flow while using edge e. Hence, if a flow f(e)
enters the edge e and f(e) is less than the designated capacity of e,
then f(e) + g(e) = 0 units of flow reach the end point of e, provided
e is used, i.e., provided f(e) != 0. In this report we study the
maximum flow problem in additive flow networks, which we prove to be
NP-hard even when the underlying graphs of additive flow networks are
planar. We also investigate the shortest path problem, when to every
edge e is assigned a cost value for every unit flow entering edge e,
which we show to be NP-hard in the strong sense even when the additive
flow networks are planar.