INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL
ISSN 1841-9836, 12(1):103-115, February 2017.

Two Flow Problems in Dynamic Networks

C. Schiopu, E. Ciurea

Camelia Schiopu*, Eleonor Ciurea
Transilvania University of Braşov
Romania, 500091 Braşov, Iului Maniu, 50
camelia.s@unitbv.ro, e.ciurea@unitbv.ro
*Corresponding author: camelia.s@unitbv.ro

Abstract: In this paper we study two flow problems: the feasible flow problem
in dynamic networks and the maximum flow problem in bipartite dynamic networks
with lower bounds. We mention that the maximum flow problem in bipartite dynamic
networks with lower bound was presented in paper [8]a. For these problems we give
examples.
Keywords: dynamic networks, feasible flow, bipartite network, maximum flow.

aReprinted (partial) and extended, with permission based on License Number
3917170356624 ©[2016] IEEE, from "Computers Communications and Control (ICCCC),
2016 6th International Conference on"

1 Introduction

The theory of flow is one of the most important parts of Combinatorial Optimization. The
static network flow models arise in a number of combinatorial applications that on the surface
might not appear to be optimal flow problems at all. The problem also arises directly in prob-
lems as far reaching as machine scheduling, the assignment of computer modules to computer
processor, tanker scheduling etc. [1]. However, in some applications, time is an essential ingredi-
ent [3], [4], [5]. In this case we need to use the dynamic network flow model. On the other hand,
the bipartite static network also arises in practical context such baseball elimination problem,
network reliability testing etc. and hence it is of interest to find fast flow algorithms for this
class of networks [1], [6].

The maximum flow problem in bipartite dynamic networks with lower bounds was presented
in paper [8]. In this paper, which is an extension of [8], we present in addition the feasible
flow problem in dynamic networks. These problem have not been treated so far. Further on, in
Section 2.1 we discuss some basic notions and results for the maximum flow problem in general
static networks with lower bounds. Section 2.2 deals with the maximum flows problem in general
dynamic networks with lower bounds. In Section 2.3 we present algorithms for flow problems
in bipartite static network and in Section 2.4 we discuss the feasible flows in static networks.
In Section 3 we discuss the feasible flows problem in dynamic network and give some examples.
Section 4 deals with maximum flows in bipartite dynamic networks with lower bounds and an
example.

2 Terminology and Preliminaries

In this section we discuss some basic notations and results used throughout the paper.

2.1 Maximum flows in static networks with lower bounds

Let G = (N,A,l,u) be a static network with the set of nodes N = {1, . . . ,n}, the set of arcs
A = {a1, . . . ,ak, . . . ,am}, ak = (i,j), i,j ∈ N, the lower bound function l : A → N, the upper

Copyright © 2006-2017 by CCC Publications



104 C. Schiopu, E. Ciurea

bound (capacity) function u : A → N, with N the natural number set, 1 the source node and n
the sink node.

For a given pair of subset X,Y of the set of nodes N of a network G we use the notation:

(X,Y ) = {(i,j)|(i,j) ∈ A,i ∈ X,j ∈ Y}

and for a given function f on set of arcs A we use the notation:

f(X,Y ) =
∑

(X,Y ) f(i,j)

A flow is a function f : A → N satisfying the next conditions:

f(i,N) −f(N,i) =




v, if i = 1
0, if i 6= 1,n
−v, if i = n

(1a)

l(i,j) ≤ f(i,j) ≤ u(i,j), (i,j) ∈ A (1b)

for some v ≥ 0. We refer to v as the value of the flow f.
The maximum flow problem is to determine a flow f for which v is maximum.
We further assume, without loss of generality, that if (i,j) ∈ A then (j,i) ∈ A (if (j,i) /∈ A

we consider that (j,i) ∈ A with l(j,i) = u(j,i) = 0).
A preflow f is a function f : A → N satisfying the next conditions:

f(N,i) −f(i,N) ≥ 0, i ∈ N −{1,n} (2a)

l(i,j) ≤ f(i,j) ≤ u(i,j), (i,j) ∈ A (2b)

For a preflow f the excess of each node i ∈ N is

e(i) = f(N,i) −f(i,N) (3)

and if e(i) > 0, i ∈ N −{1,n} then we say that node i is an active node.
Given a flow (preflow) f, the residual capacity r(i,j) of any arc (i,j) ∈ A is r(i,j) =

u(i,j) − f(i,j) + f(j,i) − l(j,i). The residual network with respect to the flow (preflow) f is
G̃ = (N,Ã,r) with à = {(i,j)|(i,j) ∈ A,r(i,j) > 0}. In the residual network G̃ = (N,Ã,r) we
define the distance function d : N → N. We say that a distance function is valid if it satisfies
the following two conditions

d(n) = 0 (4a)

d(i) ≤ d(j) + 1, (i,j) ∈ Ã (4b)

We refer to d(i) as the distance label of node i. We say that an arc (i,j) ∈ Ã is admissible
if satisfies the condition that d(i) = d(j) + 1; we refer to all other arcs as inadmissible. We also
refer to a path from node 1 to node k consisting entirely of admissilbe arcs as an admissible path.

Whereas the maximum flow problem with zero lower bounds always has a feasible solution
(since the zero flow is feasible), the problem with non-negative lower bounds could be infeasible.
Therefore the maximum flow problem with non-negative lower bounds can be solved in two
phases:

(P1) this phase determines a feasible flow if one is exists;
(P2) this phase converts a feasible flow into a maximum flow.

The problem in each phase essentially reduce to solving a maximum flow problem with zero lower
bounds. Consequently, it is possible to solve the maximum flow problem with non-negative lower
bounds by solving two maximum flow problems, each with zero lower bounds.

In the next presentation we assume familiarity with maximum flow algorithms, and we omit
many details. The reader interested in further details is urged to consult the book [1].



Two Flow Problems in Dynamic Networks 105

2.2 Maximum flows in dynamic networks with lower bounds

Dynamic network models arise in many problem settings, including production distribution
systems, economic planning, energy systems, traffic systems, and building evacuation systems
[3], [4], [5].

Let G = (N,A,l,u) be a static network with the set of nodes N = {1, . . . ,n}, the set of
arcs A = {a1, . . . ,am}, the lower bound function l, the upper bound (capacity) function u, 1 the
source node and n the sink node. Let N be the natural number set and let H = {0, 1, . . . ,T}
be the set of periods, where T is a finite time horizon, T ∈ N. Let use state the transit time
function h : A×H → N the time lower bound function e : A×H → N, the time upper bound
function q : A×H → N, e (i,j; t) ≤ q(i,j; t), for all (i,j) ∈ A and for all t ∈ H. The parameter
h(i,j; t) is the transit time needed to traverse an arc (i,j). The parameters e(i,j; t) and q(i,j; t)
represents the minimum and respective maximum amount of flow that can travel over arc (i,j)
when the flow departs from i at time t and arrives at j at time θ = t + h(i,j; t).

The maximal dynamic flow problem for T time periods is to determine a flow function g :
A×H → N, which should satisfy the following conditions in dynamic network D = (N,A,h,e,q) :

T∑
t=0

(g(1,N; t) −
∑
τ

g(N, 1; τ)) = w̄ (5a)

g(i,N; t) −
∑
τ

g(N,i; τ) = 0, i 6= 1,n, t ∈ H (5b)

T∑
t=0

(g(n,N; t) −
∑
τ

g(N,n; τ)) = −w̄ (5c)

e(i,j; t) ≤ g(i,j; t) ≤ q(i,j; t), (i,j) ∈ A , t ∈ H (6)

max w̄, (7)

where τ = t − h(k,i; τ), w̄ =
T∑
t=0

v(t), v(t) is the flow value at time t and g(i,j; t) = 0 for all

t ∈{T −h(i,j; t) + 1, . . . ,T}.
Obviously, the problem of finding a maximum flow in the dynamic network D = (N,A,h,e,q)

is more complex than the problem of finding a maximum flow in the static network G =
(N,A,l,u). Fortunately, this issue can be solved by rephrasing the problem in the dynamic
network D into a problem in the static network R1 = (V1,E1, l1,u1) called the reduced expanded
network.

The static expanded network of dynamic network D = (N,A,h,e,q) is the network R =
(V,E,l,u) with V = {it|i ∈ N,t ∈ H}, E = {(it,jθ)|(i,j) ∈ A,t ∈ {0, 1, . . . ,T − h(i,j; t)},
θ = t+h(i,j; t),θ ∈ H}, l(it,jθ) = e(i,j; t), u(it,jθ) = q(i,j; t), (it,jθ) ∈ E. The number of nodes
in the static expanded network R is n(T +1) and number of arcs is limited by m(T +1)−

∑
A

◦h(i,j),

where ◦h(i,j) = min{h(i,j; 0), . . . ,h(i,j; T)}. It is easy to see that any flow in the dynamic
network D from the source node 1 to the sink node n is equivalent to a flow in the static
expanded network R from the source nodes 10, 11, . . . , 1T to the sink nodes n0,n1, . . . ,nT and
vice versa. We can further reduce the multiple source, multiple sink problem in the static
expanded network R to a single source, single sink problem by introducing a supersource node 0
and a supersink node n + 1 constructing the static super expanded network R2 = (V2,E2, l2,u2),
where V2 = V ∪{0,n + 1}, E2 = E ∪{(0, 1t)|t ∈ H}∪{(nt,n + 1)|t ∈ H}, l2(it,jθ) = l(it,jθ),
u2(it,jθ) = u(it,jθ), (it,jθ) ∈ E, l2(0, 1t) = l2(nt,n + 1) = 0, u2(0, 1t) = u2(nt,n + 1) = ∞,
t ∈ H.



106 C. Schiopu, E. Ciurea

We construct the static reduced expanded network R1 = (V1,E1, l1,u1) as follows. We define
the function h2 : E2 −→ N, with h2(0, 1t) = h2(nt,n + 1) = 0, t ∈ H, h2(it,jθ) = h(i,j; t),
(it,jθ) ∈ E. Let d2(0, it) be the length of the shortest path from the source node 0 to the node
it, and d2(it,n + 1) the length of the shortest path from node it to the sink node n + 1, with
respect to h2 in network R2. The computation of d2(0, it) and d2(it,n + 1) for all it ∈ V are
performing by means of the usual shortest path algorithms. The network R1 = (V1,E1, l1,u1)
have V1 = {0,n + 1}∪{it|it ∈ V,d2(0, it) + d2(it,n + 1) ≤ T}, E1 = {(0, 1t)|d2(1t,n + 1) ≤ T,t ∈
H}∪{(it,jθ)|(it,jθ) ∈ E,d2(0, it)+h2(it,jθ)+d2(jθ,n+1) ≤ T}∪{(nt,n+1)|d2(0,nt) ≤ T,t ∈ H}
and l1, u1 are restrictions of l2, u2 at E1.

Now, we construct the static reduced expanded network R1 = (V1,E1, l1,u1) using the notion
of dynamic shortest path. The dynamic shortest path problem is presented in [3]. Let d(1, i; t) be
the length of the dynamic shortest path at time t from the source node 1 to the node i and d(i,n; t)
the length of the dynamic shortest path at time t from the node i to the sink node n, with respect
to h in dynamic network D. Let as consider Hi = {t|t ∈ H,d(1, i; t) ≤ t ≤ T −d(i,n; t)}, i ∈ N,
and Hi,j = {t|t ∈ H,d(1, i; t) ≤ t ≤ T −h(i,j; t) −d(j,n; θ)}, (i,j) ∈ A. The multiple sources,
multiple sinks static reduced expanded network R0 = (V0,E0, l0,u0) have V0 = {it|i ∈ N,t ∈ Hi},
E0 = {(it,jθ)|(i,j) ∈ A,t ∈ Hi,j}, l0(it,jθ) = e(i,j; t), u0(it,jθ) = u1(i,j; t), (it,jθ) ∈ E0. The
static reduced expanded network R1 = (V1,E1, l1,u1) is constructed from network R0 as follows:
V1 = V0∪{0,n+1},E1 = E0∪{(0, 1t)|1t ∈ V0}∪{(nt,n+1)|nt ∈ V0}, l1(0, 1t) = l1(nt,n+1) = 0,
u1(0, 1t) = u1(nt,n + 1) = ∞, 1t,nt ∈ V0, l1(it; jθ) = l0(it,jθ) and u1(it,jθ) = u0(it,jθ),
(it,jθ) ∈ E0.

We notice that the static reduced expanded network R1(R0) is always a partial subnetwork
of static super expanded network R2(R). In references [4], [5] it is shown that a dynamic flow
for T periods in the dynamic network D with e = 0 is equivalent with a static flow in a static
reduced expanded network R1. Since an item released from a node at a specific time does not
return to the location at the same or at an earlier time, the static networks R,R2,R0,R1 cannot
contain any circuit, and therefore, are acyclic always.

In the most general dynamic model, the parameter h (i) = 1 is waiting time at node i, and
the parameter e(i; t), q(i; t) are lower bound and upper bound for flow g(i; t) 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 flow problem for T time periods in the dynamic network D formulated in
conditions (5), (6), (7) is equivalent with the maximum flow problem in the static reduced
expanded network R0 as follows:

f0(it,V0) −f0(V0, it) =



vt, it = 1t, t ∈ H1
0, it 6= 1t,nt, t ∈ H1,

t ∈ Hn
−vt, it = nt, t ∈ Hn

(8)

l0(it,jθ) ≤ f0(it,jθ) ≤ u0(it,jθ), (it,jθ) ∈ E0 (9)

max
∑
H1

vt, (10)

where by convention it = 0 for t = −1 and it = n + 1 for t = T + 1.
In stationary case the dynamic distances d(1, i; t), d(i,n; t) become static distances d(1, i),

d(i,n).
Many notions from this section are presented and in papers [4], [7].



Two Flow Problems in Dynamic Networks 107

2.3 Maximum flows in bipartite static networks

In this section we consider that the static network G = (N,A,l,u) is bipartite static network.
A bipartite network has the set of nodes N partitioned into two subsets N1 and N2, so that for
each arc (i,j) ∈ A, either i ∈ N1 and j ∈ N2 or i ∈ N2 and j ∈ N1. Let n1 = |N1| and n2 = |N2|.
Without any loss of generality, we assume that n1 ≤ n2. We also assume that source node 1
belongs to N2 (if the source node 1 belonged to N1, then we could create a new source node
1′ ∈ N2, and we could add an arc (1′, 1) with l(1′, 1) = 0, u(1′, 1) = ∞). A bipartite network is
called unbalanced if n1 << n2 and balanced otherwise.

The observation of Gusfield, Martel, and Fernandez-Baca [6] that time bounds for several
maximum flow algorithms automatically improves when the algorithms are applied without mod-
ification to unbalanced networks. A careful analysis of the running times of these algorithms
reveals that the worst case bounds depend on the number of arcs in the longest node simple path
in the network. We denote this length by L. For general network, L ≤ n− 1 and for a bipartite
network L ≤ 2n1 + 1. Hence for unbalanced bipartite network L << n. Column 3 of Table 1
summarizes these improvements for several network flow algorithms.

Table 1: Several maximum flows algorithms

Algorithm Running time, Running time, Running time

general network bipartite network modified version

Dinic n2m n21m does not apply

Karazanov n3 n21n n1m + n
3
1

FIFO preflow n3 n21n n1m + n
3
1

Highest label n2
√
m n1n

√
m n1m

Excess scaling nm + n2 log ū n1m + n1n log ū n1m + n
2
1 log ū

Ahuja, Orlin, Stein, and Tarjan [2] obtained further running time improvements by modifying
the algorithms. This modification applies only to preflow push algorithms. They call it the two
arcs push rule. According to this rule, always push flow from a node in N1 and push flow on two
arcs at a time, in a step called a bipush, so that no excess accumulates at nodes in N2. Column
4 of Table 1 summarizes the improvements obtained using this approach.

We recall that the FIFO preflow algorithm might perform several saturating pushes followed
either by a nonsaturating push or relabeled operation. We refer to this sequence of operations
as a node examination. The algorithm examines active nodes in the FIFO order. The algorithm
maintains the list Q of active nodes as a queue. Consequently, the algorithm selects a node i
from the front of Q, performs pushes from this node, and adds newly active nodes to the rear
of Q. The algorithm examines node i until either it becomes inactive or it is relabeled. In the
latter case, we add node i to the rear of the queue Q. The algorithm terminates when the queue
Q of active nodes is empty. (see [1])

The modified version of FIFO preflow algorithm for maximum flow in bipartite network is
called bipartite FIFO preflow algorithm. A bipush is a push over two consecutive admissible
arcs. It moves excess from a node i ∈ N1 to another node k ∈ N1. This approach means that
the algorithm moves the flow over the path D̃ = (i,j,k),j ∈ N2, and ensures that no node in N2
ever has any excess. A push of α units from node i to node j decreases both e(i) and r0(i,j) by
α units and increases both e(j) and r0(j,i) by α units. (see [2])

In the paper [2] is presented the following bipartite FIFO preflow (BFIFOP) algorithm:



108 C. Schiopu, E. Ciurea

Algorithm 1 The algorithm for a feasible flow in R0.
1: ALGORITHM BFIFOP;
2: BEGIN
3: PREPROCESS;
4: while Q 6= ∅ do
5: BEGIN
6: select the node i from the front of Q;
7: BIPUSH/RELABEL(i);
8: END
9: END.

1: PROCEDURE PREPROCESS;
2: BEGIN
3: f =: 0; Q := ∅;
4: push u(1,j) units of flow on each (1,j) ∈ A and add j to rear of Q;
5: compute the exact distance labels d(i) from t to i;
6: END;

1: PROCEDURE BIPUSH/RELABEL(i);
2: BEGIN
3: if there is an admissible arc (i,j) then
4: BEGIN
5: select an admissible arc (i,j);
6: if there is an admissible arc (j,k) then
7: BEGIN
8: select an admissible arc (j,k);
9: push α := min{e(i),r(i,j),r(j,k)} units of flow along the path (i,j,k) and adds k

10: to Q if k /∈ Q;
11: END
12: else
13: d(j) := min{d(k) + 1|(j,k) ∈ A,r(j,k) > 0}
14: END
15: else
16: d(i) := min{d(j) + 1|(i,j) ∈ A,r(i,j) > 0};
17: END;

For more information see [2].
We notice the fact that have used the notations from this paper and specify that this algorithm

runs on networks G with l = 0, a single source node 1, a single sink node n.

2.4 Feasible flows in static networks

We consider the flow problem satisfying the conditions (1a) and (1b). The condition (1a) is
the flow conservation condition and the condition (1b) is the feasibility condition.

Let f be a flow of value v in the static network G = (N,A,l,u). Let be Ḡ the static network
we get by adding the return arc (n, 1) to the network G. We extend the mappings l,u and f to
Ḡ as follows:



Two Flow Problems in Dynamic Networks 109

l̄(n, 1) = 0, ū(n, 1) = ∞, f̄(n, 1) = v (11)
Then f̄ is a circulation on Ḡ:

f̄(i,N) − f̄(N,i) = 0, i ∈ N (12a)

l̄(i,j) ≤ f̄(i,j) ≤ ū(i,j) (12b)
We notice that the static network Ḡ = (N̄,Ā, l̄, ū) has N̄ = N, Ā = A ∪{(n, 1)}, l̄(i,j) =

l(i,j), ū(i,j) = u(i,j), f̄(i,j) = f(i,j), (i,j) ∈ A and usual, ∞ means a sufficiently large
number, for example ū(1,N).

Therefore the feasible flow problem we are looking for corresponding to an feasible circulation
on network Ḡ. However, note that the feasible flow problem might well be unsolvable, because
there might not be any feasible circulations.

A cut in the static network G = (N,A,l,u) is an arc set [X,Y ] = (X,Y )∪(Y,X) with X ⊂ N,
Y = N −X, (X,Y ) = {(i,j)|(i,j) ∈ A,i ∈ X,j ∈ Y}, (Y,X) = {(j,i)|(j,i) ∈ A,j ∈ Y,i ∈ X}.
The set (X,Y ) denote the set of forward arcs in the cut and the set (Y,X) denote the set of
backward arcs in the cut. We refer to a cut [X,Y ] as a 1 −n cut if 1 ∈ X and n ∈ Y . For the
maximum flow problem the capacity of 1 −n cut [X,Y ] is

c[X,Y ] = u(X,Y ) − l(Y,X) (13)
A 1 −n cut whose capacity is the minimum among all 1 −n cuts is a minimum cut.
In [1] the next theorems are proved.

Theorem 1. (Generalized Max-Flow Min-Cut Theorem). The maximum value of the flow from
a source node 1 to a sink node n in a static network G = (N,A,l,u) is equal to the capacity of
a minimum 1 −n cut.

Theorem 2. (Feasible Circulation Theorem). A necessary and sufficient condition for the exis-
tence of a feasible circulation on G = (N,A,l,u) is that l(Y,X) ≤ u(X,Y ) for any cut [X,Y ] of
G.

Theorem 3. (Feasible Flow Theorem). A necessary and sufficient condition for the existence of
a feasible flow on G = (N,A,l,u) is that l(Y,X) ≤ u(X,Y ) for all partitions N = X ∪Y with
1 /∈ Y or n /∈ X.

Theorem 3 result from Theorem 2 if transform the flow f on G = (N,A,l,u) into circulation
f̄ on Ḡ = (N̄,Ā, l̄, ū).

3 The feasible flow problem in dynamic networks

3.1 The feasible flow in dynamic networks

We consider the flow problem satisfying the conditions (5) and (6). A flow g on the dynamic
network D = (N,A,h,e,q) satisfying the conditions (5) and (6) is equivalent with the flow f0
on the multiple sources, multiple sinks static reduced expanded network R0 = (V0,E0, l0,u0)
satisfying the conditions (8) and (9).

Recall the construction of sets Hi and Hi,j: Hi = {t|t ∈ H,d(1, i; t) ≤ t ≤ T − d(i,n; t)},
i ∈ N, and Hi,j = {t|t ∈ H,d(1, i; t) ≤ t ≤ T − h(i,j; t) − d(j,n; θ)}, (i,j ∈ A). This sets
make the connection between the dynamic network D and the static network R0. Therefore we
reformulate Theorem 1, Theorem 2, Theorem 3 for the static network R0.

Let V0 be V0 = V01 ∪ . . .∪V0i ∪ . . .V0n with V0i = {it|i ∈ N,t ∈ Hi}, i = 1, . . . ,n. We refer
to a cut [X0,Y0] with X0 ⊂ V0, Y0 = V0 −X0 as a V01 −V0n cut if V01 ⊂ X0 and V0n ⊂ Y0.



110 C. Schiopu, E. Ciurea

Theorem 4. (Generalized Dynamic Max-Flow Min-Cut Theorem). The maximum value of the
flow from a source node V01 to a sink node V0n in a static network R0 = (V0,E0, l0,u0) is equal
to the capacity of a minimum V01 −V0n cut.

Theorem 5. (Feasible Dynamic Circulation Theorem). A necessary and sufficient condition for
the existance of a feasible circulation on R0 = (V0,E0, l0,u0) is that l0(Y0,X0) ≤ u0(X0,Y0) for
any cut [X0,Y0] of R0.

Theorem 6. (Feasible Dynamic Flow Theorem). A necessary and sufficient condition for the
existence of a feasible flow on R0 = (V0,E0, l0,u0) is that l0(Y0,X0) ≤ u0(X0,Y0) for all partitions
V0 = X0 ∪Y0 with V01 6⊂ Y0 or V0n 6⊂ X0.

If h,e,q are constant over time, then a dynamic network D = (N,A,h,e,q) is said to be
stationary. Ford and Fulkerson [5] have devised an algorithm that generates a maximum flow in
the stationary dynamic network D = (N,A,H, 0,q), the case when e = 0. The flow obtained
with the algorithm Ford and Fulkerson is called temporally repeated flow. Let c : A → N be the
fucntion cost. For many details is urged to consult the book [5].

There are two inconveniences for the flow problem in the stationary dynamic network D =
(N,A,h,e,q). The first is that although in the planar network G = (N,A,c, l,u) with c = h,l =
e,u = q exist a feasible flow, it is possible that in the static network R0 = (V0,E0, l0,u0) will
not be any feasible flow. The second inconvenience consist in the fact that it is possible that the
temporally repeated flow in the network R0 of a feasible and minimum time flow in the network
G = (N,A,c, l,u), will not be any feasible in the network R0.

3.2 Examples

The stationary dynamic network D = (N,A,h,e,q) is presented in Figure 1 and the time
horizon set to T = 5, therefore H = {0, 1, 2, 3, 4, 5}. The transit time h(i,j), the lower bound
e(i,j) and the upper bounds q(i,j) for all arcs (i,j) ∈ A are indicated in this order near arcs.

Figure 1: The stationary dynamic network D.

We obtain: d(1, 1) = 0,d(1, 6) = 4, d(1, 2) = 1,d(2, 6) = 3, d(1, 3) = 1,d(3, 6) = 3, d(1, 4) =
3,d(4, 6) = 1, d(1, 5) = 2,d(5, 6) = 2, d(6, 6) = 0; H1 = {0, 1}, H2 = {1, 2}, H3 = {1, 2},
H4 = {3, 4}, H5 = {2, 3}, H6 = {4, 5}; H1,2 = {0, 1}, H1,3 = {0, 1}, H2,3 = {1}, H2,4 = {1, 2},
H2,5 = {1}, H3,5 = {1, 2}, H4,6 = {3, 4}, H5,4 = {2, 3}, H5,6 = {2}.

The static network R0 = (V0,E0, l0,u0) is presented in Figure 2. The lower bounds l0(it,jθ)
and the upper bounds u0(it,jθ) for all arcs (it,jθ) ∈ E0 are indicated in this order near arcs.

For all partitions N = X ∪ Y with 1 /∈ Y or n /∈ X of the static network G = (N,A,c =
h,l = e,u = q) is verified the condition from Theorem 3. Therefore exist a feasible flow on G.
Also, is verified Theorem 6 on the network R0 = (V0,E0, l0,u0).

Example 1. We replace in the network from Figure 1 e(1, 2) = 4, q(2, 4) = 4, q(2, 5) = 4 with
e(1, 2) = 7, q(2, 4) = 2, q(2, 5) = 2. Now, we consider the partition N = X∪Y with X = {2} and



Two Flow Problems in Dynamic Networks 111

Figure 2: The static network R0.

Y = {1, 3, 4, 5, 6}. We have (X,Y ) = {(2, 3), (2, 4), (2, 5)}, (Y,X) = {(1, 2)} and in the network
G = (N,A,c = h,l = e,u = q) we obtain l(Y,X) = l(1, 2) = 7 > 6 = u(2, 3) + u(2, 4) + u(2, 5) =
u(X,Y ). Therefore not exist a feasible flow on G.

Example 2. We replace in the network from Figure 1 q(2, 4) = 4 with q(2, 4) = 3. For
q(2, 4) = 3 the Theorem 3 is verified. Therefore exist a feasible flow on network G = (N,A,c =
h,l = e,u = q). If q(2, 4) = 3 then u0(21, 43) = u0(22, 44) = 3. We consider the partition V0 =
X0 ∪Y0 with X0 = {22} and Y0 = V0 −X0. We have (X0,Y0) = {(22, 44)}, (Y0,X0) = {11, 22}
and l0(Y0,X0) = l0(11, 22) = 4 > 3 = q(2, 4) = u0(22, 44) = u0(X0,Y0). From Theorem 6 we
obtain that the flow problem in the static network R0 (dynamic network D) is infeasible.

4 Maximum flows in bipartite dynamic networks with lower bounds

4.1 Maximum flows

In this Section the dynamic network D = (N,A,h,e,q) is bipartite.
We construct the static reduced expanded network R0 = (V0,E0, l0,u0) and we notice the

fact that the network R0 is a bipartite network with V0 = W1 ∪ W2, W1 = {it|i ∈ N1, t ∈ H},
W2 = {it|i ∈ N2, t ∈ H}. Let w1,w2,ε0 be w1 = |W1|, w2 = |W2|, ε0 = |E0|. If n1 << n2 then
obvious that w1 << w2. In the static bipartite network R0 we determine a maximum flow f0
with a generalization of bipartite FIFO preflow algorithm.

We generalize the BFIFOP for a network R0 = (V0,E0, l0,u0) where l0 > 0, there are
multiple source nodes 1t, t ∈ H1 and there are multiple sink nodes nt, t ∈ Hn. Also, we present
a pseudocode in detail.

We specify that maintain the arc list E+0 (it) = {(it,jθ) |(it,jθ) ∈ E0}. We can arrange the
arcs in these lists arbitrarily, but the order, once decided, remains unchanged throughout the



112 C. Schiopu, E. Ciurea

algorithm. Each node i has a current arc, which is an arc in E+0 (it) and is the next candidate
for admissibility testing. Initially, the current arc of node it is the first arc in E

+
0 (it). Whenever

the algorithm attempts to find an admissible arc emanating from node it, it tests whether the
node’s current arc is admissible. If not, it designates the next arc in the arc list as the current
arc. The algorithm repeats this process until it either finds admissible arc or it reaches the end
of the arc list.

The generalised bipartite FIFO preflow (GBFIFOP) is presented in Algorithm 2.
We notice that any path in the residual network R̃0 = (V0, Ẽ0,r0) can have at most 2w1 + 1

arcs. Therefore we set d(1t) := 2w1 + 1 in PROCEDURE PREPROCES.
The correctness of the GBFIFOP algorithm results from correctness of the algorithm for

maximum flow in bipartite network [2].

Theorem 7. The GBFIFOP algorithm which determines a maximum flow into the bipartite
dynamic network D = (N,A,h,q) has the complexity O(n1mT2 + n31T

3).

Proof: In Section 3 we specify that the maximum flow problem for T time periods in the dynamic
network D = (N,A,h,e,q) is equivalent with the maximum flow problem in the static reduced
expanded network R0 = (V0,E0, l0,u0). The networks D and R0 are bipartite with N = N1∪N2,
V0 = W1 ∪W2. We have n1 = |N1|, n2 = |N2|, m = |A|, w1 = |W1|, w2 = |W2|,ε0 = |E0|. The
bipartite FIFO preflow algorithm determines a maximum flow into the bipartite static network
G = (N1 ∪ N2,A,l,u) in O(n1m + n31) how is specified in table from Section 4. We apply the
generalizate bipartite FIFO preflow algorithm in the static reduced expanded bipartite network
R0. Hence the algorithm has the complexity O(w1ε0 + w31). From Section 4 we have w1 = n1T
and ε0 ≤ mT . As a result the algorithm has the complexity O(n1mT2 + n31T

3).
We specify that in the first phase the feasible flow f0 is zero flow and in the second phase the

feasible flow f0 is the feasible flow f0 determined in the first phase. 2

Algorithm 2 The generalised bipartite FIFO preflow (GBFIFOP) algorithm
1: ALGORITHM GBFIFOP;
2: BEGIN
3: PREPROCESS;
4: while Q 6= ∅ do
5: BEGIN
6: select the node it from the front of Q;
7: BIPUSH/RELABEL(it);
8: END;
9: END.

1: PROCEDURE PREPROCESS;
2: BEGIN
3: f0 is a feasible flow in R0; Q := ∅;
4: compute the exact distance labels d(it);
5: for t ∈ H1 do
6: BEGIN
7: f0(1t,jθ) := u0(1t,jθ) and adds node jθ to the rear of Q for all (1t,jθ) ∈ E0
8: d(1t) := 2w1 + 1;
9: END;

10: END.



Two Flow Problems in Dynamic Networks 113

1: PROCEDURE BIPUSH/RELABEL(it);
2: BEGIN
3: select the first arc (it,jθ) in E

+
0 (it) with r0(it,jθ) > 0;

4: β := 1;
5: repeat
6: if (it,jθ) is admissible arc then
7: BEGIN
8: select the first arc (jθ,kτ ) in E

+
0 (jθ) with r0(jθ,kτ ) > 0;

9: if (jθ,kτ ) is admissible arc then
10: BEGIN
11: push α := min{e(it),r0(it,jθ),r0(jθ,kτ )} units of flow over the arcs
12: (it,jθ), (jθ,kτ );
13: if kτ /∈ Q then
14: adds node kτ to the rear of Q;
15: END
16: else if (jθ,kτ ) is not the last arc in E

+
0 (jθ) with r0(jθ,kτ ) > 0 then

17: select the next arc in E+0 (jθ)
18: else
19: d(jθ) := min{d(kτ ) + 1|(jθ,kτ ) ∈ E+0 (jθ),r0(jθ,kτ ) > 0};
20: if e(it) > 0 then
21: if (it,jθ) is not the last arc in E

+
0 (it) with r0(it,jθ) > 0 then

22: select the next arc in E+0 (jθ)
23: else
24: BEGIN
25: d(it) := min{d(jθ) + 1|(it,jθ) ∈ E+0 (jθ),r0(it,jθ) > 0};
26: β := 0;
27: END;
28: END
29: until e(it) = 0 or β = 0
30: if e(it) > 0 then
31: adds node it to the rear of Q;
32: END;

4.2 Example

We have N1 = {2, 3, 7} and N2 = {1, 4, 5, 6}.
The support digraph of the bipartite dynamic network is presented in Figure 3 and time

horizon being set T = 5, therefore H = {0, 1, 2, 3, 4, 5}. The transit times h(i,j; t) = h(i,j), t ∈
H, the lower bounds e(i,j; t) = e(i,j) and the upper bounds (capacities) q(i,j; t) = q(i,j), t ∈ H
for all arcs are indicate in Table 2.

Applying the GBFIFOP algorithm in the first phase and the second phase we obtain the
flows f0(it,jθ), f∗0 (it,jθ) (the feasible flow, the maximum flow) which are indicated in Figure
4. We have W1 = {21, 22, 23, 31, 32, 33, 73, 74, 75} and W2 = {10, 11, 12, 44, 52, 53, 54, 62,
63, 64}. A minimum (10, 11, 12)−(73, 74, 75) cut in the static network R0 is [Y0, Ȳ0] = (Y0, Ȳ0) ∪
(Ȳ0,Y0) with Y0 = {10, 11, 12, 22, 23, 31, 32, 33} and Ȳ0 = {21, 44, 52, 53, 54, 62, 63, 64, 73, 74, 75}.
Hence [Y0, Ȳ0] = {(10, 21), (22, 53), (22, 64), (23, 54), (31, 62), (31, 44), (32, 63)} ∪ {(52, 33)}. We
have w̄0 = f∗0 (Y0, Ȳ0) −f

∗
0 (Ȳ0,Y0) = 40 − 0 = 40 = u0(Y0, Ȳ0). Hence f

∗
0 is a maximum flow.



114 C. Schiopu, E. Ciurea

Figure 3: The support digraph of network D = (N,A,h,e,q)

Figure 4: The network R0 = (V0,E0,f0,f∗0 ).

Table 2: The functions h,e,q

(i,j) (1,2) (1,3) (2,4) (2,5) (2,6) (3,4) (3,6) (4,7) (5,3) (5,7) (6,7)

h(i,j) 1 1 3 1 2 3 1 1 1 1 1

e(i,j) 3 5 1 1 1 0 4 1 0 1 5

q(i,j) 12 10 8 3 3 4 5 12 3 4 10



Two Flow Problems in Dynamic Networks 115

Conclusions

In this paper we approached two flow problems: the feasible flow problem in dynamic networks
and the maximum flow problem in bipartite dynamic networks with lower bounds. For the
maximum flows problem in bipartite dynamic networks with lower bounds we developed an
algorithm. These problem have not been treated so far. We demonstrate the fact that if the
dynamic network D = (N,A,h,e,q) is bipartite, then the static reduced expanded network
R0 = (V0,E0, l0,u0) is bipartite. For solving, we have rephrased the maximum flows problem in
bipartite dynamic networks with lower bound into a problem in bipartite static network. Then,
we have extended the bipartite FIFO preflow algorithm of Ahuja et al. [2] for the static reduced
expanded network with multiple source and multiple sinks R0 = (V0,E0, l0,u0). Also we have
presented the complexity for the generalization bipartite FIFO preflow algorithm. For each of
the two problems we have presented one example.

Flow problems in bipartite dynamic networks like: the parametric maximum flow problem,
the minimum cost flow problem, the generalization of the highest label preflow push algorithm
or the generalization of the excess scaling algorithm are still open for research.

Bibliography

[1] R. Ahuja, T. Magnanti and J. Orlin (1993), Network Flows. Theory, algorithms and appli-
cations, Prentice Hall, Inc., Englewood Cliffs, New Jersey, 1993.

[2] R. Ahuja, J. Orlin, C. Stein and R. Tarjan (1994), Improved algorithms for bipartite network
flows, SIAM Journal of Computing, 23:906-933.

[3] X. Cai, D. Sha and C. Wong (2007), Time-varying Nework Optimization, Springer, 2007.

[4] E. Ciurea (2002), Second best temporally repeated flow, Korean Journal of Computational
and Applied Mathematics, 9(1):77-86.

[5] L. Ford, D. Fulkerson, Flow in Networks., Princeton University Press, Princenton, New
Jersey, 1962.

[6] D. Gusfield, C. Martel, and D. Fernandez-Baca (1987), Fast algorithms for bipartite network
flow, SIAM Journal of Computing, 16:237-251.

[7] C. Schiopu, E. Ciurea (2016), The maximum flows in planar dynamic dynamic networks,
International Journal of Computers Communications & Control, 11(2):282-291.

[8] C. Schiopu, E. Ciurea, The maximum flows in bipartite dynamic networks with lower
bounds. The static approach, Computers Communications and Control (ICCCC), 2016 6th
International Conference on, IEEE Xplore, e-ISSN 978-1-5090-1735-5, doi: 10.1109/IC-
CCC.2016.7496731, 10-15.