Minimum parametric flow in time-dependent dynamic networks

¹ Andrei Şaguna National College, Şirul Mitropolit Andrei Şaguna 1, Braşov 500123, Romania
² Transilvania University of Braşov, Bulevardul Eroilor 29, Braşov 500036, Romania

^* Corresponding author: parpalea@gmail.com

Received: 12 September 2017
Accepted: 20 February 2018

Abstract

The paper presents a dynamic solution method for the parametric minimum flow in time-dependent, dynamic network. This approach solves the problem for a special parametric dynamic network with linear lower bound functions of a single parameter. Instead of directly working in the original network, the method implements a labelling algorithm which works in the parametric dynamic residual network where repeatedly decreases the flow along quickest dynamic source-sink paths for different subintervals of parameter values, in their increasing order. In each iteration, the algorithm computes both the parametric minimum flow within a certain subinterval, and the new subinterval for which the flow needs to be computed.