https://doi.org/10.31449/inf.v44i3.1907 Informatica 44 (2020) 303–310 303
Minimum Flows in Parametric Dynamic Networks - the Static Approach
Grigora¸ s (Avesalon) Nicoleta
Transilvania University of Bra¸ sov, 50091 Bra¸ sov, Iuliu Maniu, 50, Romania
E-mail: nicole.grigoras@gmail.com
Keywords: dynamic network, parametric network, minimum ﬂow
Received: October 15, 2018
The problems of ﬂows in parametric networks extend the classical problems of optimal ﬂow to some special
kind of networks where capacities of certain arcs are not constants but depending on several parameters.
Consequently, these problems consist of solving a range of ordinary (nonparametric) optimal ﬂow problems
for all the parameter values within certain sub-intervals of the parameter values. Although classical
network ﬂow models have been widely used as valuable tools for many applications [1], they fail to capture
the essential property of the dynamic aspect of many real-life problems, such as trafﬁc planning, production
and distribution systems, communication systems, evacuation planning, etc. In all these cases, time is an
essential component, either because the ﬂows take time to pass from one location to another, or because
the structure of the network changes over time. Accordingly, the dynamic ﬂow models seem suited to catch
and describe different real-life dynamic problems such as network-structure changing over time or timely
decision-making, but, because of their complexity, these models have not been as thoroughly investigated
as those of classical ﬂows.
This article presents and solves the problem of the minimum ﬂows in a parametric dynamic network. The
proposed approach consists in applying a parametric ﬂow algorithm in the reduced expended network
which is obtained by expanding the original dynamic network. A numerical example is also presented for
a better understanding of the used approach.
Povzetek: V ˇ clanku je predstavljena metoda za rešitev problema najmanjšega pretoka v parametriˇ cnih
dinamiˇ cnih mrežah.
1 Introduction
The parametric maximum ﬂow problem, as well as that
of the related minimum ﬂow one represent generalizations
of ordinary problems for the maximum, respectively min-
imum ﬂow in which the upper/lower bounds of some arcs
depend on a single parameter, being monotonically increas-
ing (or decreasing) functions of the parameter. For the
parametric maximum ﬂow problem with zero lower bounds
and linear capacity functions of a single parameter, G.Ruhe
proposed [16] an original ’piece-by-piece’ approach while
papers [11] and [13] solves the problems of parametric
minimum, respectively maximum ﬂows via an partition-
ing approach. Finally, the same partitioning approach is
extended to a discrete time dynamic network in paper [3].
This class of problems is known as the ﬂow in parametric
networks problem. Beside the applications of the ordinary,
nonparametric ﬂow problems, the applications of those of
ﬂows in parametric networks may include: multiprocessor
scheduling with release times and deadlines, integer pro-
gramming problems, computing sub-graph density and net-
work vulnerability and partitioning a data base between fast
and slow memory, product selection, ﬂow sharing, database
record segmentation in large shared databases, optimizing
ﬁeld repair kits, etc.[15]
Besides this, the static network ﬂow models arise in a num-
ber of combinatorial applications that on the surface might
not appear to be maximum ﬂow problems at all. The prob-
lem also arises directly in problems as far reaching as ma-
chine scheduling, the assignment of computer modules to
computer processors, tanker scheduling etc. [1]. How-
ever, in some other applications, time is an essential in-
gredient, whether it involves problems like maximum or
minimum ﬂows in time-varying networks [2], [3], dynamic
ﬂows of minimum cost [12], general problems of tempo-
rally repeated ﬂows [6] such as earliest arrival ﬂow [17] or
dynamic resource allocation problem for large-scale trans-
portation network evacuation [7]. Starting from the com-
plexities of the classic algorithms, an important series of
other papers concern with the complexities of dynamic net-
work algorithms. Cai et al. [4] proved that the complexity
of ﬁnding a shortest (quickest) dynamic ﬂow augmenting
path, by exploring the forward and reverse arcs succes-
sively, is O(nmT
2
). For algorithms which explores the
two sub-networks (the forward sub-network, consisting of
the set of direct arcs and the reverse sub-network consist-
ing of the set of reverse arcs simultaneously, Miller-Hooks
and Patterson [8] also reported a complexity ofO(n
2
T
2
).
By using special node addition and selection procedures,
Nasrabadi and Hashemi [9] succeeded to reduce signif-
icantly the number of node time pair that needs to be
visited. The worst-case complexity of their algorithm is
304 Informatica 44 (2020) 303–310 G.A. Nicoleta
O(nT (n +T )). Finally, Orlyn reported [10] an extremely
good running time ofO(nm) for the problem of maximum
ﬂow. In this case we need to use dynamic network ﬂow
models. Due to the powerful versatility of dynamic ﬂow
algorithms, it is not surprising that these algorithms are of-
ten more difﬁcult to design than their static counterparts
[10] but still they are also very challenging problems.
The approaches for solving the minimum parametric ﬂow
over time problem via applying classical algorithms can be
grouped in two main categories:
i) by applying a non-parametric minimum dynamic ﬂow
algorithm [12] in dynamic residual networks generated by
partitioning the interval of the parameter values [9], [14].
This ﬁrst category approach was also used [3] for ﬁnding
a maximum parametric ﬂow in discrete-time dynamic net-
works;
ii) by applying a static (classical sequential or parallel [5])
parametric ﬂow algorithm for the maximum [13], [16] or
for the minimum [11] ﬂow in a (static network) reduced ex-
pended network, which is obtained by expanding the orig-
inal dynamic network.
In this paper, the case of the minimum ﬂows in parametric
dynamic networks is considered. The proposed approach
consists in transformation of the problem of minimum ﬂow
in parametric dynamic network into that of the minimum
ﬂow in parametric static network. This problem gener-
alizes the problems of ﬂow in dynamic network and of
ﬂow in parametric static networks through the following
assumptions: (1) the dynamic network and corresponding
expanded static network are with lower bounds, (2) we ad-
dress the minimum ﬂow problem on a dynamic network
with time varying transit times as well as time varying
lower and upper bounds on arc i.e. the dynamic network
is not stationary.
The remainder of this paper is organized as follows. In Sec-
tion 2 some dynamic network notations and terminology
are presented. Then, in Section 3 we expose, the minimum
ﬂow in parametric static network, while in Section 4 the
minimum ﬂow in parametric dynamic network problem is
presented. In Section 5 an example is given. In the pre-
sentation to follow, some familiarity with ﬂow problems is
assumed and many details are omitted.
2 The minimum ﬂows in dynamic
networks.
Let G = (N;A;l;u) be a static network with the
nod set N = f1;:::;i;:::;j;:::;ng, the arc set A =
fa
1
;:::;a
k
;:::;a
m
g;a
k
= (i;j), the lower bound function
l : A ! R
+
and the upper bound (capacity) function
u : A!R
+
, whereR is the real number set. To deﬁne
the minimal static ﬂow problem, we distinguish two spe-
cial nodes in the static networkG = (N;A;l;u): a source
node 1 and a sink noden.
LetN be the natural number set and letH =f0; 1;:::Tg
be the set of periods, where T is a ﬁnite time horizon,T2
N. Let h : A  H ! N be the transit time function,
l
h
: A  H ! R
+
the time lower bound function and
u
h
: A  H !R
+
the time upper bound function. For
each arc (i;j)2A theh(i;j;t) represents the transit time
of arc (i;j) at timet,t2H.
A dynamic ﬂow from source node 1 to sink node n is
any ﬂow from 1 to n in which not less thanl
h
(i;j;t) and
not more than u
h
(i;j;t) ﬂow units starting from node i
at time t and arriving at node j at time   = t +h(i;j;t)
for all arcs (i,j) and all t. The minimal dynamic ﬂow
problem for T time periods is to determine a ﬂow function
f
h
: A  H ! N, which should satisfy the following
conditions in dynamic networkG
h
= (N;A;h;l
h
;u
h
):
P
T
t=0
(
P
j
f
h
(i;j;t)  P
k
P
  f
h
(k;i;  )) =vH ,
i = 1, (2.1.a)
P
j
f
h
(i;j;t)  P
k
P
  f
h
(k;i;  )) = 0,
i6= 1;n;t2H, (2.1.b)
P
T
t=0
(
P
j
f
h
(i;j;t)  P
k
P
  f
h
(k;i;  )) =  vH ,
i =n, (2.1.c)
l
h
(i;j;t)  f
h
(i;j;t)  u
h
(i;j;t),
8(i;j)2A and8t2H (2.2)
minvH , (2.3)
where   = t  h(k;i;  ), v
H
=
P
T
t=0
v(t), v(t) is
the ﬂow value at time t and f
h
(i;j;t) = 0, (i;j) 2 A,
t2fT  h(i;j;t) + 1;:::;Tg.
Obviously, the problem of ﬁnding a minimum dy-
namic ﬂow is more complex than the problem of ﬁnd-
ing a minimum static ﬂow. Fortunately, this complica-
tion can be solved by rephrasing the dynamic ﬂow prob-
lem into a static ﬂow problem in a static network G
0
=
(N
0
;A
0
;l
0
;u
0
) called reduced expanded network. First, we
form the expanded networkG
H
= (N
H
;A
H
;l
H
;u
H
) with
N
H
= fi
t
ji 2 N;t 2 Hg, A
H
= f(i
t
;j
  )j(i;j) 2
A;t = 0; 1;:::;T   h(i;j;t)g, l
H
(i
t
;j
  ) = l
h
(i;j;t),
u
H
(i
t
;j
  ) =u
h
(i;j;t), (i
t
;j
  )2A
H
.
We have jN
H
j = n(T + 1) and jA
H
j   m(T + 1)   P
A
 h(i;j), where
 h(i;j) =
minfh(i;j; 0);:::;h(i;j;T )g. Clearly, any dynamic
ﬂow from the source node 1 to the sink node n in
dynamic network G
h
is equivalent to a static ﬂow
from the source nodes 1
0
; 1
1
;:::; 1
T
to the sink nodes
n
0
;n
1
;:::;n
T
in static network G
H
and vice versa [2].
We can further reduce the multiple source, multiple
sink problem in network G
H
to the single source, sin-
gle sink problem by introducing a supernode 1
  and
a supersink node n
  building superexpanded network
G
  H
= (N
  H
;A
  H
;l
  H
;u
  H
), whereN
  H
= N
H
[f1
  ;n
  g,
A
  H
= A
H
[f(1
  ; 1
t
)jt 2 Hg[f(n
t
;n
  )jt 2 Hg,
l
  H
(i
t
;j
  ) = l
H
(i
t
;j
  ), u
  H
(i
t
;j
  ) = u
H
(i
t
;j
  ),
(i
t
;j
  ) 2 A
H
, l
  H
(1
  ; 1
t
) = l
  H
(n
t
;n
  ) = 0,
u
  H
(1
  ; 1
t
) =u
  H
(n
t
;n
  ) =1,t2H.
Minimum Flows in Parametric Dynamic Networks. . . Informatica 44 (2020) 303–310 305
Next, we build the reduced expanded network G
0
=
(N
0
;A
0
;l
0
;u
0
) as follows. We deﬁne the function h
  ,
h
  : A
  H
! N, h
  (1
  ; 1
t
) = h
  (n
t
;n
  ) = 0, t2 H,
h
  (i
t
;j
  ) =h(i;j;t), (i
t
;j
  )2A
H
. Letd
  (1
  ;i
t
) be the
length of the shortest path from the source node 1
  to the
nodei
t
andd
  (i
t
;n
  ) the length of the shortest path from
nodei
t
to the sink noden
  with respect toh
  in network
G
  H
.
The computation ofd
  (1
  ;i
t
) andd
  (i
t
;n
  ),i
t
2N
  H
is
performed by means of the usual shortest path algorithms
[1]. In network G
0
we rewrite the nodes 1
  ;n
  by 1
0
re-
spectivelyn
0
.
We obtain N
0
= f1
0
;n
0
g [ fi
t
ji
t
2
N
H
;d
  (1
  ;i
t
) +d
  (i
t
;n
  )   Tg, A
0
= f(1
0
; 1
t
)j1
t
2
N
H
;d
  (1
t
;n
  )  Tg[f(n
t
;n
0
)jn
t
2 N
H
;d
  (1
  ;n
t
)  Tg[fi
t
;j
  )j(i
t
;j
  ) 2 A
H
;d
  (1
  ;i
t
) + h
  (i
t
;j
  ) +
d
  (j
  ;n
  )  Tg andl
0
;u
0
are restriction ofl
  H
;u
  H
atA
0
.
It is easy to see that the networkG
0
is always a partial
sub-network ofG
  H
. Since an item released from a node at
a speciﬁc time does not return to that location at the same or
an earlier time, the networksG
H
,G
  H
,G
0
cannot contain
any circuit, and are therefore always acyclic.
In the most general dynamic model, the parameter
h(i) = 1 is the waiting time at node i, and the param-
eters l
h
(i;t);u
h
(i;t) are deﬁned as lower bound and up-
per bound, which represents the minimum respectively the
maximum amount of ﬂow that can wait at node i from time
t to t+1. This most general dynamic model is not discussed
in this paper.
The maximum dynamic ﬂow problem for T time periods
in dynamic network G
h
formulated in conditions (2.1),
(2.2), (2.3) is equivalent with the maximum static ﬂow
problem in static networkG
0
as follows:
P
j
  f
0
(it;j
  )  P
f
0
(k  ;it) =
8
<
:
v
0
, ifit = 1
0
, (2.4.a)
0, ifit6= 1
0
,n
0
, (2.4.b)
  v
0
, ifit =n
0
, (2.4.c)
l
0
(it;j
  )  f
0
(it;j
  )  u
0
(it;j
  ), (it;j
  )2A
0
, (2.5)
minv
0
, (2.6)
where by conventioni
t
= 1
0
fort =  1 andi
t
=n
0
for
t = T + 1. For further details we recommend the works
[2], [3], [4], [6], [7], [17].
3 The minimum ﬂow in parametric
static networks
A natural generalization of the minimum ﬂow problem
in static networks can be obtained by making the lower
bounds of some arcs function of a single parameter. Since
the minimum ﬂow value function in a parametric network
is a continuous piecewise linear function of the parameter,
the parametric minimum ﬂow problem can alternately be
deﬁned as to ﬁnd all the breakpoints and their correspond-
ing minimum ﬂow and maximum cuts. The approach pre-
sented in this section is presented in [11], the ﬁrst approach
for minimum ﬂow in parametric static network.
A static network G = (N;A;l;u) with the lower
boundsl(i;j) of some arcs (i;j)2 A, functions of a real
parameter   is referred to as a parametric static network
and is denoted by
  G = (N;A;
 l;u). The upper bound
function
 l :A  R
+
!R
+
is deﬁned by the relation:
 l(i;j;  ) =l0(i;j) +    L(i;j),  2 [0;  ] = I (3.1)
where L : A! R is the parametric part of the upper
bound function
 l and l
0
: A! R
+
is the non paramet-
ric part of the function
 l with
 l(i;j; 0) = l
0
(i;j), (i;j)2
A. The L(i;j) and l
0
(i;j) must satisfy  l
0
(i;j)=    L(i;j)  (u(i;j)  l
0
(i;j))=  and 0  l
0
(i;j)  u(i;j),
(i;j)2A.
The minimum ﬂow problem in parametric static network
  G = (N;A;
 l;u) is to compute all minimum ﬂows for
every possible value of  inI :
P
j
  f(i;j;  )  P
k
  f(k;i;  ) =
8
<
:
 v(  ), if i=1 (3.2.a)
0, ifi6= 1;n (3.2.b)
   v(  ), if i=n (3.2.c)
 l(i;j;  )    f(i;j;  )  u(i;j), (i;j)2A , (3.3)
min  v(  ) (3.4)
For the minimum ﬂow problem in the parametric
static network
  G = (N;A;
 l;u), the sub-intervals
I
k
= [  k
;  k+1
], k = 0; 1;:::;K of the parameter   values can be determined such as a maximum 1  n cut
in the nonparametric static network G
k
= (N;A;l
k
;u),
l
k
(i;j) =
 l(i;j;  k
), remains the maximum 1  n cut for
  2I
k
. A parametric 1  n cut in parametric static network
  G = (N;A;
 l;u) can be deﬁned as a ﬁnite set of cuts
[S
k
;T
k
],k = 0; 1;:::;K together with a partitioning of the
intervalI in disjoints subintervalsI
k
,k = 0; 1;:::;K, such
that I = I
0
[I
1
[:::[I
K
. The [S
k
;T
k
] is denoted by
[S
k
;I
k
] for eachk;k = 0; 1;:::;K The capacity of [S
k
;I
k
]
is deﬁned as:
 c[S
k
;I
k
] =
P
(S
k
;T
k
)
 l(i;j;  )  P
(T
k
;S
k
)
u(i;j),
k = 0; 1;:::;K (3.5)
A parametric maximum 1  n cut in network G
k
is
denoted by [S
  k
;I
k
], k = 0; 1;:::;K: For
  f in parametric
network
  G = (N;A;
 l;u) the parametric residual capacity
 r(i;j;  ), (i;j)2A is given by:
 r(i;j;  ) =u(j;i)    f(j;i;  ) +
  f(i;j;  )   l(i;j;  ),
  2I
k
,k = 0; 1;:::;K (3.6)
For a ﬂow
  f in parametric static network
  G, we deﬁne
the set  s(i;j) = f  j r(i;j;  ) > 0g, (i;j) 2 A. The
306 Informatica 44 (2020) 303–310 G.A. Nicoleta
static network
~
  G = (N;
~
A,  r), with
~
A =f(i;j)j(i;j)2
A;  s(i;j)6=  g is named the parametric residual static net-
work. If (i;j)2A and (i;j) = 2
~
A, then  s(i;j) =  .
Let
~
  P be a directed path from the source node 1 to the
sink noden in the parametric residual static network
~
  G. If
~
  P veriﬁes the restriction:
 s(
~
  P ) =
T
~  P
 s(i;j)6=  (3.7)
then
~
  P is named conditional decreasing directed path.
The parametric residual capacity of a conditional decreas-
ing directed path
~
  P is  r(
~
  P ;  ) = minf r(i;j;  )j(i;j)2
~
  P;  2  s(
~
  P )g. From paper [11] we have the theorem:
Theorem 1 (11). A ﬂow
  f is a minimum ﬂow in paramet-
ric static network
  G if and only if the parametric resid-
ual static network
~
  G contains no conditional decreasing
directed path
~
  P .
If residual static network
~
  G contains no conditional
decreasing path
~
  P , then the minimum ﬂow in parametric
network
  G is computed as:
  f(i;j;  ) =
 l(i;j;  )+maxf r(i;j;  )  u(j;i)+
 l(j;i;  ); 0g
(3.8)
The ﬁrst phase of ﬁnding a minimum ﬂow in network
  G
consists in establishing a feasible ﬂow, if one exists, in non-
parametric network
^
G = (N;A;
^
l;u) with
^
l(i;j) =l
0
(i;j)
for L(i;j)   0 and
^
l(i;j) = l
0
(i;j) +     L(i;j) for
L(i;j) > 0. After a nonparametric feasible ﬂow
^
f (see
[1]) we compute the parametric residual network
~
  G
0
for
this ﬂow
^
f.
The parametric residual capacities in
~
  G
0
can be written
as  r
0
(i;j;  ) =   0
(i;j) +    0
(i;j), where   0
(i;j) =
u(j;i)   ^
f(j;i) +
^
f(i;j)   l
0
(i;j) and   0
(i;j) =
L(i;j);  2I
0
= [0;  1
].
The second phase of the algorithm starts with the para-
metric residual network
~
  G
0
,  0
= 0 andI
0
= [0;  ] .
The algorithm for minimum ﬂow in a parametric static
network (the algorithm MFPSN) is presented in Figure
3.1.
(01) Algorithm MFPSN;
(02) BEGIN
(03) compute a feasible ﬂowf0 in networkG0;
(04) compute parametric residual network
~
  G0;
(05) B:=f0g;k := 0;  k
:= 0;
(06) REPEAT
(07) SDDP( k,  k
, B);
(08) k:=k+1;
(09) UNTIL(  k
=   );
(10) END.
Figure 3.1.a. The algorithm for the minimum ﬂow in
parametric static network
(01) PROCEDURE SDDP( k,  k
, B);
(02) BEGIN
(03) compute the network
~
  G
k
;
(04) compute exact distance labels
~
d(i) in
~
  G
k
;
(05) p=( n+1,..., n+1);  k
(
~
  P ) := 0;  k
(
~
  P ) := 0;
(06)   k+1
:=   ;j:=n;
(07) WHILE
~
d(n)<n DO
(08) BEGIN
(09) IF(exists an admissible arc (i;j))
(10) THEN BEGIN
(11) p(i):=j;
(12) j:=i;
(13) IF( j=1)
(14) THEN BEGIN
(15) RCDADP(p,  k+1
,B,  k
(
~
 P ),  k
(
~
 P ));
(16) j:=n;
(17) END;
(18) END
(19) ELSE BEGIN
(20)
~
d(j) :=minf
~
d(i) + 1j(i;j)2
~
A
k
g ;
(21) IF j6= n
(22) THEN j:= p(j);
(23) END;
(24) END;
(25) compute the ﬂow
  f
k
;
(26) add  k+1
to the list B;
(27) END;
Figure 3.1.b. The Procedure Shortest Decreasing Di-
rected Path (SDDP)
(01) PROCEDURE RCDADP(p,  k+1
, B,  k
(
~  P),  k
(
~  P));
(02) BEGIN
(03) compute
~
  P based on p;
(04)   k
(
~
  P ) :=minf  k
(i;j)j(i;j)2
~
  Pg;
(05)   k
(
~
  P ) :=minf  k
(i;j)j(i;j)2
~
  Pg;
(06) i:=1;
(07) WHILE i6= n DO;
(08) BEGIN
(09) IF(  k
(p(i);i)<  k
(
~
  P )
(10) THEN BEGIN
(11)   0
:=  k
+ (  k
(i;p(i))    k
(
~
 P))=(
   k
(
~
 P)    k
(i;p(i)));
(12) IF (  0
<  k+1
)
(13) THEN  k+1
:=  0
;
(14) END;
(15)   k
(i;p(i)) :=  k
(i;p(i))    k
(
~
  P );
  k
(i;p(i)) :=  k
(i;p(i))    k
(
~
  P );
(16)   k
(p(i);i) :=  k
(p(i);i) +  k
(
~
  P );
  k
(p(i);i) :=  k
(p(i);i) +  k
(
~
  P );
(17) i:=p( i);
(18) END;
(19) END;
Figure 3.1.c. The Procedure Residual Capacity of Con-
ditional Decreasing Directed Path( RCDADP).
In order to avoid working with piecewise linear func-
tions, the algorithm MFPSN works in parametric residual
static networks deﬁned for sub-intervals of the parameter
Minimum Flows in Parametric Dynamic Networks. . . Informatica 44 (2020) 303–310 307
values where the parametric residual capacities of all arcs
remain linear functions. The parametric residual network
~
  G for a sub-intervalI
k
= [  k
;  k+1
] is denoted by
~
  G
k
. In
k-th step of the algorithm MFPSN, the SDDP procedure
computes the parametric residual static network
~
  G
k
where
 r
k
(i;j;  ) =  k
(i;j) + (      k
)    k
(i;j), with  k
(i;j) =
  0
(i;j) +  k
  0
(i;j),  k
(i;j) =  0
(i;j) and computes the
shortest decreasing directed path
~
  P in network
~
  G
k
. The
RCDADP procedure computes  r
k
(
~
  P;  ),  k+1
and alters
  k
(i;p(i)),  k
(i;p(i)),  k
(p(i);i),  k
(p(i);i). Obviously
in
~
  G
k
we have  r
k
(
~
  P;  ) =  k
(
~
  P ) + (      k
)    k
(
~
  P ).
In paper [11] the following two theorems are presented.
Theorem 2 (Theorem of Correctness). The algorithm MF-
PSN computes correctly a minimum ﬂow in parametric
static network
  G = (N;A;
 l;u) and  2I = [0;  ] .
Theorem 3 (Theorem of Complexity). The algorithm MF-
PSN runs in O(Kn
2
m) time, where K+1 is the number of  value in the set B at the end of the algorithm.
For further details of this section we recommend the
work [11].
We remark the fact that the maximum ﬂow problem in
the nonparametric static network can be solved inO(nm)
time (see [10]). In this case the algorithm MFPSN runs in
O(Knm) time.
4 The minimum ﬂow in parametric
dynamic networks
A dynamic network G
h
= (N;A;h;l
h
;u
h
) for which
the lower bounds l
h
(i;j;t) of some arcs (i;j) 2 A are
functions of a real parameter   2 I = [0;  ] is referred
to as a parametric dynamic network and is denoted by
  G
h
= (N;A;h;
 l
h
;u
h
). The parametric lower bound
function
 l
h
:A  H  I!R
+
is deﬁned by the relation:
 l
h
(i;j;t;  ) =l
0h
(i;j;t) +    L
h
(i;j;t),
(i;j)2A,t2H,  2I, (4.1)
The parametric partL
h
(i;j;t) and thel
0h
(i;j;t), must
satisfy the constraints:
  l
0h
(i;j;t)=    L
h
(i;j;t)
L
h
(i;j;t)  (u
h
(i;j;t)  l
0h
(i;j;t))=  ; and
0  l
0h
(i;j;t)  u
h
(i;j;t),
(i;j)2A,t2H.
The minimum ﬂow problem in parametric dynamic
network G
h
= (N;A;h;
 l
h
;u
h
) is to compute ﬂow
function
  f
h
:A  H  I!R
+
that satisﬁes the following
constraints:
P
T
t=0
(
P
j
 f(i;j;t;  )  P
k
P
   f
h
(k;i;  ;  ) =  v
H
(  ),
i = 1 (4.4.a)
P
j
 f(i;j;t;  )  P
k
P
   f
h
(k;i;  ;  ) = 0,
i6= 1,n;t2H (4.2.b)
P
T
t=0
(
P
j
 f(i;j;t;  )  P
k
P
   f
h
(k;i;  ;  ) =   v
H
(  ),
i =n (4.2.c)
 l
h
(i;j;t;  )    f
h
(i;j;t;  )  u
h
(i;j;t),
(i;j)2A ,t2H,  2I (4.3)
min  vH (  );  2I (4.4)
where
  f
h
(i;j;t;  ) = 0, (i;j)2A,t2fT  h(i;j;t)+
1;:::;Tg,  2I.
In network
  G
h
= (N;A;h;
 l
h
;u
h
) we consider the fol-
lowing assumption: if (i;j)2 A then (j;i)2 A. This
assumption is non-restrictive because if (i;j) 2 A and
(j;i) = 2 A we consider that (j;i)2 A with
 l
h
(j;i;  ;  ) =
u
h
(j;i;  ) = 0,   = t + h(i;j;t), t 2 H,   2 I,
h(j;i;  ) =   h(i;j;t), if 0   t   T  h(i;j;t) and
h(j;i;  ) =1, ifT  h(i;j;t) + 1  t  T .
The parametric dynamic residual capacities with respect
to given ﬂow
  f
h
are deﬁned as follow:
 r
h
(i;j;t;  ) = u
h
(j;i;t)    f
h
(j;i;t;  ) +
  f
h
(i;j;t;  )   l
h
(i;j;t;  ),
(i;j)2A,t2H,  2I (4.5)
For the minimum ﬂow in parametric dynamic network
  G
h
= (N;A;h;
 l
h
;u
h
) with respect to given ﬂow
  f
h
is
deﬁned as
~
  G
h
= (N;
~
A;  r
h
), where
~
A =f(i;j)j(i;j)2
A;  r
h
(i;j;t;  )> 0;t2H;  2Ig.
In this paper, the proposed approach consists in applying
the algorithm MFPSN presented in Section 3 in paramet-
ric static reduced expanded network
  G
0
= (N
0
;A
0
;
 l
0
;u
0
)
which is constructed similar with construction of the net-
workG
0
= (N
0
;A
0
;l
0
;u
0
) presented in Section 2.
The algorithm for the minimum ﬂow in parametric dy-
namic network (the algorithm MFPDN) is presented in Fig-
ure 4.1.
(1) ALGORITHM MFPDN;
(2) BEGIN
(3) construct the network
  G
0
;
(4) apply the algorithm MFPSN in network
  G
0
;
(5) END.
Figure 4.1. The algorithm for minimum ﬂow in paramet-
ric dynamic network.
Theorem 4 (Theorem of Correctness). The algorithm MF-
PDN computes correctly a minimum ﬂow in parametric dy-
namic network
  G
h
= (N;A;h;
 l
h
;u
h
) and  2I.
Proof. This theorem results from the fact that the minimum
ﬂow in parametric dynamic network with lower bounds
  G
h
= (N;A;h;
 l
h
;u
h
) is equivalent with the maximum
ﬂow in parametric static network
  G
0
= (N
0
;A
0
;l
0
;  u
0
) and
Theorem 2.
308 Informatica 44 (2020) 303–310 G.A. Nicoleta
Theorem 5 (Theorem of Complexity). The algorithm MF-
PDN runs inO(KT
3
n
2
m) time, where K+1 is the number
for  values in the setB at the end of the algorithm.
Proof. From Theorem 3 results that the algorithm MFPSN
runs in O(K(n
0
H
)
2
m
0
H
) time. From Section 2 we obtain
n
0
=O(nT ) andm
0
=O(mT ). Therefore we obtain that
algorithm MFPDN runs inO(KT
3
n
2
m) time.
In accordance with the remark in Theorem 3, we note
that the algorithm MFPDN runs inO(KnmT
2
) time.
5 Example
The support parametric dynamic network is presented in
Figure 5.1.(a) and the time horizon is set to T = 3,
therefore H=f0; 1; 2; 3g. The transit times h(i;j;t) and
the dynamic upper bounds (capacities)u
h
(i;j;t), as well
as the parametric dynamic lower bounds
 l
h
(i;j;t;  ) =
l
0h
(i;j;t) +    L
h
(i;j;t) the for all arcs in
  G
h
are in-
dicated in the two tables in Figure 5.1.b. The interval of
parameter  values is set to [0; 1], i.e.,   =1.
(i;j) h(i;j;t) U
h
(i;j;t)
(1; 2)
1;t = 0
2;t = 1; 2; 3
5
(1; 3)
1;t = 0; 1
2;t = 2; 3
5
(2; 3) 1;t = 0; 1; 2; 3 5
(2; 4)
1;t = 0; 1
2;t = 2; 3
5
(3; 4)
2;t = 0; 1
1;t = 2; 3
5
(i;j) l
0h
(i;j;t) L
h
(i;j;t)
(1; 2)
3;t = 0
0;t = 1; 2; 3
  2;t = 0
0;t = 1; 2; 3
(1; 3)
1;t = 0; 1
0;t = 2; 3
4;t = 0
1;t = 1
0;t = 2; 3
(2; 3) 0;t = 0; 1; 2; 3
3;t = 1
0;t = 0; 2; 3
(2; 4) 0;t = 0; 1; 2; 3 0;t = 0; 1; 2; 3
(3; 4)
0;t = 0
2;t = 1; 2
0;t = 3
  2;t = 2
0;t = 0; 1; 3
(b)
Figure 5.1. The parametric dynamic network
  G
h
.
The support graph for parametric super-extended net-
work
  G
  H
is presented in Figure 5.2.
Figure 5.2. The support graph for
parametric superextended network
  G
  H
.
The support graph for parametric reduced expanded net-
work
  G
0
is showed in Figure 5.3.
Figure 5.3. The support graph for
parametric reduced expanded network
  G
0
.
The lower bounds
 l
0
(i
t
;j
  ;  ) =l
0
(i
t
;j
  ) +    L
0
(i
t
;j
  )
and the parametric upper bounds u
0
(i
t
;j
  ) for all arcs in
  G
0
are indicated in table from Figure 5.4.
(it;j
  ) l
0
(it;j
  ) L
0
(it;j
  ) u
0
(it;j
  )
^
f
0
(it;j
  )
(1
0
; 1
0
) 0 0 1 10
(1
0
; 1
1
) 0 0 1 2
(1
0
; 2
1
) 3 -2 5 5
(1
0
; 3
1
) 1 3 5 5
(1
1
; 3
2
) 1 1 5 2
(2
1
; 3
2
) 0 3 5 3
(2
1
; 4
2
) 0 0 5 2
(3
1
; 4
3
) 2 0 5 5
(3
2
; 4
3
) 2 -2 5 5
(4
2
; 4
0
) 0 0 1 2
(4
3
; 4
0
) 0 0 1 10
Figure 5.4. The
 l
0
(i
t
;j
  ;  ) = l
0
(i
t
;j
  ) +
 L
0
(i
t
;j
  );u
0
(i
t
;j
  ) and
^
f
0
(i
t
;j
  ) in network
  G
0
.
In the ﬁrst phase we determine in static residual net-
work
~
^
G
0
:
~
^
P
0
1
= (1
0
; 1
0
; 2
1
; 4
2
; 4
0
), ^ r
0
(
~
^
P
0
1
) = 2 ;
~
^
P
0
2
=
(1
0
; 1
0
; 3
1
; 4
3
; 4
0
), ^ r
0
(
~
^
P
0
2
) = 5;
~
^
P
0
3
= (1
0
; 1
1
; 3
2
; 4
3
; 4
0
),
^ r
0
(
~
^
P
0
3
) = 2;
~
^
P
0
4
= (1
0
; 1
0
; 2
1
; 3
2
; 4
3
; 4
0
), ^ r
0
(
~
^
P
0
4
) = 3. The
feasible ﬂow
^
f
0
in network
^
G
0
is presented in the table from
Figure 5.4.
Minimum Flows in Parametric Dynamic Networks. . . Informatica 44 (2020) 303–310 309
In the second phase by applying algorithm MF-
PSN in network
  G
0
we obtain in the parametric static
residual network
~
  G
0
the following directed path:
~
  P
0
1
= (1
0
; 1
1
; 3
2
; 2
1
; 4
2
; 4
0
),
~
  P
0
2
= (1
0
; 1
0
; 2
1
; 4
2
; 4
0
),
~
  P
0
3
= (1
0
; 1
0
; 3
1
; 4
3
; 4
0
),
~
  P
0
4
= (1
0
; 1
0
; 2
1
; 3
2
; 4
3
; 4
0
) in
~
  G
0
0
,
~
  G
1
,
~
  G
2
. The results of this example are synthetically
indicated in the table from Figure 5.5. The graphic of
 v
0
(  ) is presented in Figure 5.6.
k   k
~
  P
0
i
 r
k
(
~
  P
0
i
)   k+1
 v
0
(  )
~
  P
0
1
1    1
0 0
~
  P
0
2
1 +  1 6    ~
  P
0
3
3 1=4
~
  P
0
4
1 +  1=4
~
  P
0
1
1    1
1 1=4
~
  P
0
2
1 +  1 5 + 3  ~
  P
0
3
4  4  1
~
  P
0
4
1 +  3=5
~
  P
0
1
1 +  1
2 3=5
~
  P
0
2
1 +  1 2 + 8  ~
  P
0
3
4  4  1
~
  P
0
4
4  4  1
Figure 5.5. Results of applying the algorithm in
  G
0
.
Figure 5.6. The graphic of  v
0
(  )
References
[1] Ahuja R., Magnanti T., Orlin J. (1993) Network
Flows. Theory, algorithms and applications, Prentice
Hall, Inc., Engleewood Clifss, New Jersey.
[2] Aronson J.A. (1989) A survey of dynamic net-
works ﬂows, Annals of Operations Research,
20 (5), pp.1–66.https://doi.org/10.1007/
bf02216922
[3] Avesalon N., Ciurea E., Parpalea M. (2017),
Maximum parametric ﬂow in discrete-time dy-
namic networks, Fundamenta Informaticae, 156
(2), pp.125–139.https://doi.org/10.1007/
bf02216922
[4] Cai X., Sha D., Wong C. (2007) Time-varying Net-
work Optimization, Springer.
[5] Ciurea E., Ciupal˘ a L. (2004) Sequential and
parallel algorithms for minimum ﬂow, Journal
of Applied Mathematics and Computing, 15(1-
2), pp.53–75.https://doi.org/10.1007/
bf02935746
[6] Ciurea E. (2002) Second best temporally repeated
ﬂows, The Korean Journal of Computational and Ap-
plied Mathematics, 9(1), pp.77–86.https://doi.
org/10.1007/bf03012341
[7] He X., Zheng H., Peeta S. (2015) Model and solu-
tion algorithm for the dynamic resource allocation
problem for large-scale transportation network evac-
uation, Transportation Research Part C.: Emerg-
ing Technologies, 59, pp.233–247.https://doi.
org/10.1016/j.trc.2015.05.005
[8] Miller-Hooks E., Patterson S.S. (2004) On solving
quickest time problems in time-dependent dynamic
networks, Journal of Mathematical Modelling and
Algorithms, 3, pp.39–71.https://doi.org/10.
1023/b:jmma.0000026708.57419.6d
[9] Nasrabadi E., Hashemi S.M. (2010) Minimum cost
time-varying network ﬂow problems, Optimization
Methods and Software, 25 (3), pp.429–447.https:
//doi.org/10.1080/10556780903239121
[10] Orlin J. (2013) Max Flows in O(nm) time, or
better, Proceeding of the forty-ﬁfth Annual ACM
Symposium on Theory of Computing, ACM Press,
New York, pp.765–774.https://doi.org/10.
1145/2488608.2488705
[11] Parpalea M., Ciurea E. (2016) Minimum parametric
ﬂow. A partitioning approach, British Journal of
Applied Science and Technology, 13 (6), pp.1–
8.https://doi.org/10.9734/bjast/
2016/22636
[12] Parpalea M., Ciurea E. (2011) The quickest maximum
dynamic ﬂow of minimum cost, International Jour-
nal of Applied Mathematics and Informatics, 3 (5),
pp.266–274.
[13] Parpalea M., Ciurea E. (2013), Partitioning algorithm
for the parametric maximum ﬂow, Applied Math-
ematics, 4 (10A), pp.3–10.https://doi.org/
10.4236/am.2013.410a1002
310 Informatica 44 (2020) 303–310 G.A. Nicoleta
[14] Parpalea M., Avesalon N., Ciurea E. (2018)
Minimum parametric ﬂow in time depen-
dent dynamic networks, Revue d’Automatique,
d’Informatique et de Recherche Opérationnelle
- Theoretical Informatics and Applications
(RAIRO: ITA), 52 (1), pp.43–53.https:
//doi.org/10.1051/ita/2018002
[15] Rashidi H., Tsang E. (2015) Vehicle Scheduling in
Port Automation: Advanced Algorithms for Minimum
Cost Flow Problems, CRC Press, 2 edition, Boca Ra-
ton, London, New York.https://doi.org/10.
1201/b18984
[16] Ruhe G. (1991) Algorithmic Aspects of Flows in
Networks, Kluwer Academic Publisher, Dordrecht,
The Netherlands.https://doi.org/10.1007/
978-94-011-3444-6
[17] Zheng H., Chiu Y .C., Mirchandani P.B. (2015) On
the System Optimum Dynamic Trafﬁc Assignment
and Earliest Arrival Flow Problems, Transportation
Science, 49, pp.13–27.https://doi.org/10.
1287/trsc.2013.0485