Bulletin of the Transilvania University of Bra sov Vol XX(YY), No.ABC – 2018 [625463]

Bulletin of the Transilvania University of Bra sov Vol XX(YY), No.ABC – 2018
Series III: Mathematics, Informatics, Physics, xx-xx
PARAMETRIC FLOWS IN STATIC NETWORKS
Mircea PARPALEA1
Abstract
In our everyday lives we encounter many dierent types of real networks,
including electrical networks, telephone cable, highway networks, railways,
manufacturing networks or computer networks. Flow networks are very use-
ful to model any real world problems which confronts to any \commodity"

owing through a network (pipes, electric wires, highways, rails, and so on).
Generally, networks consist of special points called nodes and links con-
necting pairs of nodes called arcs. Network
ow problems have always been
among the best studied [1] combinatorial optimization problems. Maximum

ow problem is the classical network
ow problems in network
ow theory
and has been extensively investigated. In this problem, the maximum
ow
which can be moved from the source to the sink is calculated without ex-
ceeding the maximum capacity. Once, the maximum
ow problem is solved
it can be used to solve other network
ow problems also [14].
Parametric
ows problems may be regarded as some extensions of the
classical maximum/minimum
ow problems in which the capacities of cer-
tain arcs are not xed but are functions of a parameter. Consequently, these
problems consist in solving several nonparametric, ordinary maximum/min-
imum
ow problems for all the parameter values within certain subintervals
of the parameter values. During last few decades, researches that have been
made resulted in new solution methods and in improvements of the algo-
rithms for known methods. This paper presents the continuous improve-
ments that have been made during the last years as well as recent techniques
and algorithms related to parametric maximum and minimum
ow problems.
2000 Mathematics Subject Classication: 90B10, 90C35, 90C47.
Key words: maximum / minimum
ow, parametric network, network
partitioning algorithms.
1National College Andrei S aguna , Bra sov, Romania, e-mail: [anonimizat]

Parametric
ows in static networks 1
1 Indroduction
The parametric maximum
ow problem, as well as that of the related mini-
mum
ow one represent generalizations of ordinary problems for the maximum,
respectively minimum
ow in which the upper/lower bounds of some arcs depend
on a single parameter, being monotonically increasing (or decreasing) functions
of the parameter.
Beside the applications of the ordinary maximum/minimum
ows, those of para-
metric
ows include: multiprocessor scheduling with release times and deadlines
[10], integer programming problems [2], computing sub-graph density and net-
work vulnerability and partitioning a data base between fast and slow memory
[3], product selection [5], [20],
ow sharing [10], database record segmentation in
large shared databases [9], and optimizing eld repair kits [16].
For the parametric maximum
ow problem, Gallo, Grigoriadis and Tarjan [10]
uses a modied version of the push-relabel method using amortization and graph
contraction and obtain an algorithm that solves the parametric maximum
ow
problem in the same asymptotic running time as the original algorithm. Apply-
ing their idea on the network of King, Rao and Tarjan [15] they obtained the same
O(nm
logm=(nlogn )n) complexity limit for the parametric
ow problem as for the
ordinary maximum
ow problem.
Using a \divide and conquer" approach that uses an ordinary push-relabel al-
gorithm [12] on a network with nvertices,marcs, and integer upper bounds
bounded by U, Tarjan et al. [23] achieved a running time which is bounded by
O(min
n2=3;m1=2

m
log(n2=m)
logU ), that is by a factor (i.e. minfn;log (nU)g)
worse than that of the ordinary maximum
ow algorithm [11].
For the parametric maximum
ow problem with linear capacity functions of a
single parameter, Hamacher and Foulds [13]investigated an augmentation paths
approach for determining in each iteration an improvement of the
ow dened
on the whole interval of the parameter. For the same problem, Ruhe [21], [22]
proposed a \piece-by-piece" approach which assumes that the maximum
ow is
known for a given value of the parameter and computes the supplementary maxi-
mum
ow to be added to the current
ow in order to preserve the optimality of the

ow for greater parameter values and also the maximum value of the parameter
for which the computed
ow is maximal.
Zhang, Ward and Feng [24], [25] proposed a balancing technique based algorithm
for the parametric
ow problem in a special bipartite network. With an enhance-
ment suggested by Tarjan et al.[23] the algorithm runs in O(mn2
log(nU)) time.
The partitioning type approach, which will be presented in this paper, proposes
original algorithms for computing both maximum and minimum
ows in paramet-
ric networks with linear upper / lower bound functions of a single parameter. As
Bichot and Siarry showed, the parametric
ow problem \is of genuine practical

2 Mircea Parpalea
and theoretical interest since graph partitioning applications are described on a
wide variety of subjects as: data distribution in parallel-computing, VLSI circuit
design, image processing, computer vision, route planning, air trac control, mo-
bile networks, social networks, etc" [4].
The rest of this paper has the following structure and content. Section 2 reviews
the preliminaries and terminology for ordinary
ows in static networks, as follows:
Subsection 2.1 deals with maximum
ow in static networks and Subsection 2.2 is
dedicated to the minimum
ow in static networks. Section 3 describes in its Sub-
section 3.1 the parametric maximum
ow problem while the parametric minimum

ow problem is described in Subsection 3.2. Subsection 3.3 presents some per-
sonal, ecient implementations of the aproaches that resolves the parametric
ow
problem in static networks. Finally, Section 4 contains some concluding remarks
and original examples which ilustrate the partitioning aproach for the parametric
maximum and minimum
ow in static network.
2 Terminology and preliminaries
Given a capacitated network G= (N;A;`;u;s;t ) withN=f:::;i;:::gbeing
the set of nodes iandA=f:::;a;:::gbeing the set of arcs aso that for every
a2A,a= (i;j) withi;j2N, letn=jNjandm=jAj. The upper bound
function and the lower bound function are two nonnegative functions, u(a) and
`(a) associated with each arc a= (i;j)2A. The network has two special nodes:
a source node sand a sink node t. A
ow is a function f:A!<+satisfying the
next conditions:
X
jj(i;j)2Af(i;j)X
jj(j;i)2Af(j;i) =8
<
:v; i =s
0; i6=s;t
v; i =t(1)
for somev0, wherevis referred to as the value of the
ow f. Any
ow on a
directed network satisfying the
ow bound constraints:
`(i;j)f(i;j)u(i;j);8(i;j)2A (2)
for every arc ( i;j)2Ais referred to as a feasible
ow .
Acutis a partition of the node set Ninto two subsets SandT=NS,
denoted by [ S;T]. Alternatively, a cut can be dened as the set of arcs whose
endpoints belong to dierent subsets SandT. An arc (i;j)2Awithi2Sand
j2Tis referred to as a forward arc of the cut while an arc ( i;j)2Awithi2T
andj2Sas a backward arc of the cut. Let ( S;T) denote the set of forward arcs
in the cut and let ( T;S) denote the set of backward arcs. A cut [ S;T] is anst
cut ifs2Sandt2T.

Parametric
ows in static networks 3
2.1 Maximum
ows in static networks
The maximum
ow problem is to determine a
ow ~ffor whichvis maximized.
For a feasible
ow fin network G= (N;A;`;u;s;t ), the residual capacity of any
arc (i;j)2Afor the maximum
ow problem represents the maximum additional

ow that can be sent from node ito nodejover both arcs ( i;j) and (j;i). For the
maximum
ow problem, the residual capacity ~r(i;j) of any arc ( i;j)2A, with
respect to a given
ow f, is given by:
~r(i;j) =u(i;j)f(i;j) +f(j;i)`(j;i): (3)
For a network G= (N;A;`;u;s;t ) and a feasible solution f, the network denoted
by~G(f) = (N;~A), where ~Ais the set of residual arcs (i;j) with ~r(i;j)>0
is referred to as the residual network with respect to the given
ow ffor the
maximum
ow problem. From the residual capacities ~ r(i;j), the
ow can be
determined using the following expression:
f(i;j) =`(i;j) +maxfu(i;j)~r(i;j)`(i;j);0g: (4)
For the maximum
ow problem, the capacity ~ c[S;T] of anstcut [S;T] is dened
as:
~c[S;T] =u(S;T)`(T;S): (5)
Thestcut with the lowest capacity value among all stcuts is referred to as
aminimum cut [~S;~T].
Theorem 1. (Max-Flow Min-Cut Theorem): If there is a feasible
ow in the
network, the value of the maximum
ow from a source sto a sinktin a capacitated
network equals the capacity of the minimum stcut,~v= ~c[~S;~T].
A path inG= (N;A;`;u;s;t ) from the source node sto the sink node tis
referred to as an augmentation path if the corresponding directed path in the
residual network consists only of arcs with positive residual capacities. There is
a one-to-one correspondence between augmentation paths PinGand directed
paths ~Pfromstotin the residual network ~G(f). For a directed path ~Pin~G(f)
we have ~r(~P) = minf~r(i;j)j(i;j)2~Pg.
Theorem 2. (Augmentation Path Theorem): A
ow ~fis a maximum
ow if and
only if the residual network ~G(~f)contains no directed path from the source node
to the sink node.
2.2 Minimum
ows in static networks
The minimum
ow problem is to determine a
ow ^ffor whichvis minimized.
The problem can be solved in two phases:
(1) establishing a feasible
ow;
(2) from a given feasible
ow, establishing the minimum
ow. For the rst phase
see the algorithm presented in [1].

4 Mircea Parpalea
Letfbe a feasible solution for the minimum
ow problem in network G=
(N;A;`;u;s;t ). Supposing that an arc ( i;j)2Acarriesf(i;j) units of
ow,
the residual capacity of any arc ( i;j)2A, with respect to the given
ow f, for
the minimum
ow problem, represents the maximum amount of
ow by which the

ow from node ito nodejcan be decreased over both arcs ( i;j) and (j;i). The
residual capacity ^r(i;j) of any arc ( i;j)2Ais given by:
^r(i;j) =u(j;i)f(j;i) +f(i;j)`(i;j): (6)
For a network G= (N;A;`;u;s;t ) and a feasible solution f, the network denoted
by^G(f) = (N;^A), where ^Ais the set of residual arcs corresponding to the feasible
solutionfand consisting only of arcs ( i;j) with ^r(i;j)>0, is referred to as the
residual network with respect to the given
ow ffor the minimum
ow problem.
The capacity of an stcut ^c[S;T] is dened, for the minimum
ow problem, as:
^c[S;T] =`(S;T)u(T;S): (7)
Thestcut with the greatest capacity value among all stcuts is referred to
as a maximum cut and is denoted by [ ^S;^T].
Theorem 3. (Min-Flow Max-Cut Theorem): If there is a feasible
ow in the
network, the value of the minimum
ow from a source sto a sinktin a capacitated
network with nonnegative lower bounds equals the capacity of the maximum st
cut.
A path inG= (N;A;`;u;s;t ) from the source node sto the sink node tis
referred to as a decreasing path if the corresponding directed path in the residual
network consists only of arcs with positive residual capacities. There is a one-
to-one correspondence between decreasing paths PinGand directed paths ^P
fromstotin the residual network ^G(f). For a directed path ^Pin^G(f) we have
^r(^P) = minf^r(i;j)j(i;j)2^Pg.
Theorem 4. (Decreasing Path Theorem): A
ow ^fis a minimum
ow if and
only if the residual network ^G(^f)contains no directed path from the source node
to the sink node.
3 Parametric
ows in static networks
The problem of parametric
ows in static networks concerns with the gen-
eral problem of parametric
ows. Given a capacitated directed network with
non-negative capacities and/or lower bounds, the natural generalization of the
ordinary maximum/minimum
ow in static
ows problem is obtained by mak-
ing the upper/lower bounds for some of the network arcs linearly depend of a
single, non-negative, real parameter. The general parametric
ow problem is to
compute the maximum/minimum
ows for every possible value of the parameter
within a given interval. The above mentioned problem looks like the ordinary

Parametric
ows in static networks 5
maximum/minimum
ow problem in static networks with the decisive dierences
that the
ow variables of the parametric problem are piecewise linear functions
instead of real numbers and the upper/lower bounds are linear functions instead
of constants.
Denitions included in the following sections are taken from/adapted after, refer-
ences [18] and [17] while the proof for theorems can be found in reference [19].
3.1 Parametric maximum
ows in static networks
The parametric maximum
ow problem consists in transforming the clas-
sic problem of maximum
ows in networks by adapting it to a network G=
(N;A;`;u;s;t ) where the upper bounds of some arcs ( i;j)2Aare depending of
a real parameter.
Denition 1. A directed network G= (N;A;`;u;s;t )for which the upper bounds
uof some arcs (i;j)2Aare functions of a real parameter is referred to as a
parametric network and is denoted by G= (N;A;`; u;s;t ).
For a parametric network G, the parametric upper bound (capacity) function
u:A[0;]!<+of an arc (i;j)2Acomputes the real numbers  u(i;j;),
called upper bound of arc ( i;j), for all the parameter values in a given interval
[0;]:
u(i;j;) =u0(i;j) +
U(i;j)`(i;j); forall2[0;]: (8)
Here,U:A!< is a real valued function associating to each arc ( i;j)2Athe real
numberU(i;j), referred to as the parametric part of the upper bound of the arc
(i;j). Obviously, the nonnegative value u0(i;j) is the upper bound value of the arc
(i;j) computed for for = 0, i.e. u(i;j; 0) =u0(i;j). From the above mentioned
restriction, derives that the parametric part of the upper bounds U(i;j) must
satisfy the constraint: U(i;j)(`(i;j)u0(i;j))=,8(i;j)2A. The parametric

ow value function  v:N[0;]!< associates to each of the nodes i2Na real
number v(i;) called value of node ifor each of the parameter values.
Denition 2. A feasible
ow in parametric network G= (N;A;`; u;s;t )is called
parametric
ow and is dened as a function f:A[0;]!<+satisfying the
following constraints:
X
jj(i;j)2Af(i;j;)X
jj(j;i)2Af(j;i;) = v(i;);8i2N;82[0;]: (9)
`(i;j)f(i;j;)u(i;j;);8(i;j)2A;82[0;]: (10)
whereP
i2Nv(i;) = 0 ,82[0;].

6 Mircea Parpalea
The parametric maximum
ow (PMaxF) problem is to compute all maximum

ows for every possible value of the parameter, i.e. 82[0;]:
maximize v()forall2[0;]; (11)
X
jj(i;j)2Af(i;j;)X
jj(j;i)2Af(j;i;) =8
<
:v(); i =s
0; i6=s;t
v(); i =t;(12)
`(i;j)f(i;j;)u(i;j;);8(i;j)2A; (13)
LetFdenote the set of piecewise linear functions fiwithfi: [0;]! <+.
An ordering relation over the elements of Fis dened as: fifj
fi()
fj()forall2[0;]:If the two piecewise linear functions fiandfjhave at least
a breakpoint then neither fifjnorfifjhold for the entire interval [0 ;] and
consequently, the two functions may not necessarily be comparable. For the case
when two piecewise linear functions have a number of K crossing points taking
place for the values k,k= 1;


;Kof the parameter, the interval [0 ;] can be
partitioned in K+ 1 subintervals of the type k;k+1,k= 0;


;K, with0= 0
andK+1= , so that within every subinterval one of the following two cases
to hold:fifjorfifj, i.e. the two linear functions to become comparable
within subintervals.
Denition 3. A parametric stcut partitioning, denoted by [Sk;Jk],k=
0;


;K, is dened as a nite set of cuts [Sk;Tk]together with a partitioning
of the interval [0;]of the parameter in disjoints subintervals Jk= [k;k+1], so
thatJ0[


[JK= [0;].
Denition 4. For the parametric maximum
ow problem, the capacity ~c[Sk;Jk]
of a parametric stcut partitioning is a linear function on every subinterval Jk,
k= 0;


;K, dened as:
~c[Sk;Jk] =X
(i;j)2(Sk;Tk)u(i;j;)X
(j;i)2(Tk;Sk)`(j;i); k= 0;


;K: (14)
Denition 5. A parametric stcut partitioning [Sk;Jk]with the subintervals Jk
assuring that every cut is a minimum cut [~Sk;~Tk]within the subinterval [k;k+1]
is referred to as a parametric minimum stcut and is denoted by [~Sk;Jk],k=
0;


;K.
Theorem 5. (Parametric max-
ow min-cut theorem [19]): If there is a feasible

ow in the parametric network G, the value function ~vof the parametric maximum

ow~ffrom a source sto a sinktequals the capacity ~cof the parametric minimum
stcut[~Sk;Jk],k= 0;


;K.

Parametric
ows in static networks 7
Denition 6. For the parametric maximum
ow problem, the parametric residual
capacity ~r(i;j;)of any of the arcs (i;j)2Awith respect to a given parametric

ow frepresents the maximum additional
ow that can be sent from node ito
nodejover the arcs (i;j)and(j;i)and is given by:
~r(i;j;) = u(i;j;)f(i;j;) +f(j;i;)`(i;j): (15)
The subintervals ~I(i;j)[0;] for (i;j)2A, where ~r(i;j;)>0, i.e. an
augmentation of the
ow f(i;j;) is possible along the arc ( i;j), are dened as
~I(i;j) =fj~r(i;j;)>0g.
Denition 7. Given a feasible
ow fin the parametric network G, the network
denoted by~G(f) = (N;~A(f))with ~A(f) =n
(i;j)j(i;j)2A;~I(i;j)6=;o
being the
set consisting only of arcs with positive parametric residual capacities, is referred
to as the parametric residual network with respect to the given
ow ffor the
parametric maximum
ow problem.
If an arc (i;j)2Adoes not belong to~G(f) then ~I(i;j) :=;is set.
Denition 8. A conditional augmentation directed path is denoted by~Pand is a
directed path ~Pfrom the source sto the sink tin the parametric residual network
~G(f)with the restriction that:
~I(~P) =\
(i;j)2~P~I(i;j)6=;: (16)
Denition 9. The parametric residual capacity of a conditional augmentation
directed path~Prepresents the minimum value of the parametric residual capacity
~r(i;j;)among all arcs (i;j)composing the conditional augmentation directed
path for all the parameter values in the subinterval ~I(~P):
~r(~P;) = min
(i;j)2~Pn
~r(i;j;)j2~I(~P)o
: (17)
Theorem 6. (Conditional augmentation path theorem [19]): A parametric
ow
~fis a maximum parametric
ow if and only if the parametric residual network
~G(~f)contains no conditional augmentation directed path.
3.2 Parametric minimum
ows in static networks
The parametric minimum
ow problem can be regarded as a generalisation of
the non-parametric, ordinary minimum
ow problem for the case of the parametric
networks where the lower bounds of some or all arcs ( i;j)2Adepend of a
nonnegative real parameter . For the parametric minimum
ow problem, a
parametric network denoted by G= (N;A; `;u;s;t ) represents a directed network
for which the lower bounds of some arcs depend of a real parameter.

8 Mircea Parpalea
Denition 10. In a parametric network G= (N;A; `;u;s;t ), the parametric
lower bound function `:A[0;]!<+of an arc (i;j)2Acomputes the real
numbers `(i;j;), called lower bound of arc (i;j), for all the parameter values
in a given interval [0;]:
`(i;j;) =`0(i;j)
L(i;j)u(i;j); forall2[0;]: (18)
In the above expression, L:A!< denotes a real valued function which is
called the parametric part of the lower bound of the arc ( i;j)2Aand which
must meet the following condition: [ `0(i;j)u(i;j)]=L(i;j)`0(i;j)=,
8(i;j)2A. Evidently, `0(i;j) represents the value of the function `(i;j;) for
= 0 and consequently, it must hold that 0 `0(i;j)u(i;j),8(i;j)2A.
The parametric minimum
ow (PMinF) problem consists in solving the nonpara-
metric minimum
ow problem for all the parameter values within a certain interval
[0;]:
minimize v()forall2[0;]; (19)
`(i;j;)f(i;j;)u(i;j);8(i;j)2A; (20)
under restrictionsand (12).
Denition 11. For the parametric minimum
ow problem, the capacity ^c[Sk;Jk]
of a parametric stcut partitioning is a linear function on every subinterval Jk,
k= 0;


;K, dened as:
^c[Sk;Jk] =X
(i;j)2(Sk;Tk)`(i;j;)X
(j;i)2(Tk;Sk)u(j;i); k= 0;


;K: (21)
Denition 12. A parametric stcut partitioning [Sk;Jk]with the subintervals Jk
assuring that every cut is a maximum cut [^Sk;^Tk]within the subinterval [k;k+1]
is referred to as a parametric maximum stcut and is denoted by [^Sk;Jk],
k= 0;


;K.
Theorem 7. (Parametric min-
ow max-cut theorem [19]): If there is a feasible

ow in the parametric network G, the value function ^vof the parametric minimum

ow^ffrom a source sto a sinktequals the capacity ^cof the parametric maximum
stcut[^Sk;Jk],k= 0;


;K.
Denition 13. For the parametric minimum
ow problem, the parametric resid-
ual capacity ^r(i;j;)of any of the arcs (i;j)2Awith respect to a given parametric

ow frepresents the maximum amount by which the
ow sent from node ito node
jcan be decreased over the arcs (i;j)and(j;i)and is given by:
^r(i;j;) =u(j;i)f(j;i;) +f(i;j;)`(i;j;): (22)
The subintervals ^I(i;j)[0;] for (i;j)2A, where ^r(i;j;)>0, i.e. a
decrease of the
ow f(i;j;) is possible along the arc ( i;j), are dened as ^I(i;j) =
j^r(i;j;)>0
.

Parametric
ows in static networks 9
Denition 14. Given a feasible
ow fin the parametric network G, the network
denoted by^G(f) = (N;^A(f))with ^A(f) =n
(i;j)j(i;j)2A;^I(i;j)6=;o
being the
set consisting only of arcs with positive parametric residual capacities, is referred
to as the parametric residual network with respect to the given
ow ffor the
parametric minimum
ow problem.
Denition 15. A conditional decreasing directed path is denoted by^Pand is a
directed path ^Pfrom the source sto the sink tin the parametric residual network
^G(f)with the restriction that:
^I(^P) =\
(i;j)2^P^I(i;j)6=;: (23)
Denition 16. The parametric residual capacity of a conditional decreasing di-
rected path^Prepresents the minimum value of the parametric residual capacity
^r(i;j;)among all arcs (i;j)composing the conditional decreasing directed path
for all the parameter values in the subinterval ^I(^P):
^r(^P;) = min
(i;j)2^Pn
^r(i;j;)j2^I(^P)o
: (24)
Theorem 8. (Conditional decreasing path theorem [19]): A parametric
ow^fis
a minimum parametric
ow if and only if the parametric residual network^G(^f)
contains no conditional decreasing directed path.
3.3 Algorithmic approaches for the parametric
ows in static net-
works
The current section presents several dierent approaches that have been pro-
posed for solving the parametric
ows problem in static networks.
The " Shortest conditional decreasing path algorithm " for the para-
metric minimum
ow problem [7] determines in each stage an improvement of the

ow over the subinterval of the parameter values which derives directly from a
shortest conditional decreasing directed path in the parametric residual network.
In its rst phase, the algorithm establishes a feasible
ow, if such a
ow exists
in the given parametric network. In the second phase, the algorithm repeatedly
searches a shortest conditional decreasing directed path and, when one is found,
the
ow is decreased along the corresponding paths in the original parametric
network and the parametric residual network is updated. As soon as the sink
node cannot be reached from the source, the algorithm stops and the obtained

ow represents a parametric minimum
ow.

10 Mircea Parpalea
1Shortest conditional decreasing path algorithm
2begin
3 nd a feasible
ow f0in network G=
N;A; `;u;s;t
;
4 compute the parametric residual network^G(f0);
5 repeat
6 compute the minimum length ( h) of a conditional decreasing directed path;
7 if(exists ( ^In1;h6=;) within the
ow can be improved) then
8 begin
9 build the conditional decreasing directed path^P;
10 compute the parametric residual capacity ^r(^P;);
11 update the parametric residual network ;
12 end;
13 until (h=n1) and ( ^In1;h=;);
14end.
The " Sequential algorithm " for the parametric minimum
ow problem [6]
is based on a " piece-by-piece " approach which seeks, in each of its steps, a max-
imum improvement of the
ow and the next maximum interval of the parameter
ensuring the computed
ow to be a parametric minimum
ow. Assuming that
the minimum
ow is known for a given value of the parameter the following two
subproblems have to be solved: computing the maximum amount of
ow that has
to be subtracted from the current
ow in order that this to preserve its optimality
for greater parameter values; computing the maximum value of the parameter
for which the newly computed
ow remains optimal. The algorithm consists in
applying a non-parametric, ordinary maximum
ow algorithm for a sequence of
parameter values in increasing order. An initial minimum
ow is computed for a
given value of the parameter and then the algorithm repeatedly nds a maximum
amount by which the
ow can be decreased over the next interval of the parameter
values so that the maximum cut not to change. This maximum amount of
ow
is computed as a maximum
ow in a derived network G
kwith properly set lower
and upper bounds:
`
k(i;j) = 0 for ^f(i;j;k) =u(i;j);
`
k(i;j) =1 for ^f(i;j;k)<u(i;j).
u
k(i;j) =L(i;j) for ^f(i;j;k) =`(i;j;k);
u
k(i;j) =1 for ^f(i;j;k)>`(i;j;k).
On each of its iterations, the algorithm computes a new breakpoint of the piecewise
linear minimum
ow value function and the corresponding parametric minimum

ow.

Parametric
ows in static networks 11
1Sequential algorithm for parametric minimum flow
2begin
3 nd a feasible
ow f0in network G0=
N;A; `(= 0);u;s;t
;
4k:= 0;k:= 0;
5 compute the MINIMUM
ow ^fkin network G0;
6 whilek<do
7 begin
8 compute the derived network G
k;
9 compute the MAXIMUM
ow ~f
kin network G
k;
10 compute the parameter subinterval kthat mentain the optimality of ^fk;
11 ^fk+1:=^fkk
~f
k;
12 k+1:=k+k;
13 k:=k+ 1;
14 end
15end.
A parametric bipartite network is called monotone if the lower bounds of the
out of the source arcs are non-increasing functions of a parameter, the lower
bounds of the arcs into the sink are non-decreasing functions of the parameter,
while the lower bounds of the remaining arcs are constants. The " Balancing
algorithm " for the minimum
ow problem in monotone parametric bipartite
networks decreases the
ow over simple decreasing directed paths. The proposed
algorithm [8] does not work directly in the original network but in the parametric
residual network and nds a particular state of the residual network from which
the minimum
ow and the maximum cut for any of the parameter values are ob-
tained. The approach implements a round-robin algorithm looping over a list of
nodes until an entire pass ends without changes of the
ow.
The " Partitioning algorithm " for the parametric maximum
ow [18] /
minimum
ow [17] problem represents an original approach of the directed paths
type algorithms. From a feasible
ow, established in the rst stage of the algo-
rithm, the partitioning algorithm nds, on every iteration of its second stage, an
augmentation/decreasing directed path from the source node to the sink node in
a parametric residual network dened for only a subinterval of the parameter val-
ues, improves the
ow along the corresponding paths in the original parametric
network and splits the interval of the parameter values into subintervals which
are generated by the breakpoints of the piecewise linear parametric residual ca-
pacity function of the augmentation/decreasing directed path. Further on, the
algorithm reiterates within each of the generated subintervals, in increasing order
of the parameter values.

12 Mircea Parpalea
1Partitioning algorithm
2begin
3 nd a feasible
ow f0in network G;
4k:= 0;k:= 0;
5 repeat
6 compute the parametric residual network Gk(f0);
7k+1:= ;
8 while (exists a directed path Pin network Gk(f0))do
9 begin
10 build a directed path Pin network Gk(f0);
11 compute the parametric residual capacity  r(P);
12 compute the upper limit k+1that maintain the linearity of ^fk;
13 update the the parametric residual network Gk(fk);
14 end;
15 compute the optimal
ow for Jk= [k;k+1];
16k:=k+ 1;
17 until (k= );
18end.
The " Parametric min-max algorithm " [19] solves the minimum
ow problem
in a parametric network with linear lower bound functions by computing a para-
metric maximum
ow from the sink node to the source node. Given a feasible

ow, a minimum
ow from the source node to the sink node can be determined by
establishing a maximum
ow from the sink node to the source node in the resid-
ual network dened as for the parametric maximum
ow problem. The algorithm
does not work directly in the original parametric network but in the parametric
residual network dened as for the parametric maximum
ow problem.
1Parametric min-max algorithm
2begin
3 nd a feasible
ow f0in network G;
4 compute the parametric residual network~G(f0);
5 compute the parametric MAXIMUM
ow f:=~ffromttosin~G(f0);
6^f:=fis a parametric MINIMUM
ow from stotin network G;
7end.
4 Concluding remarks
The main advantage of the partitioning approach consists in operating with
linear functions instead of the hardly handling piecewise linear functions, i.e. the
residual capacity of every arc in the residual network is explicitly written as a

Parametric
ows in static networks 13
linear function. Even though considering both the upper bounds and the lower
ones as parametric linear functions instead of constants, the parametric residual
capacity of every arc in the residual network still remains written as a linear func-
tion, allowing the running of the algorithm in a similar manner.
Based on the fact that the partitioning approach for the parametric
ow prob-
lem is based on algorithms which work in the parametric residual network, the
changes that follow from taking into account both upper and lower parametric
bounds are equally treated and thus, easy to be dealt with. Consequently, the
presented algorithms can be extended to networks with both lower and upper
parametric bounds. Following from the above considerations, the partitioning al-
gorithms remain valid (with appropriate modications) for the cases of parametric
both upper bounds and lower bounds.
Further on, we will illustrate the partitioning algorithm for the parametric maxi-
mum
ow in the static network presented in Figure 1 with the source node s= 0
and the sink node t= 3. The parameter takes values in the interval [0 ;1], i.e.
 = 1.
Figure 1: The parametric network G= (N;A; `;u;s;t ). Above each arc ( i;j), the parametric
lower bound function `(i;j;), the feasible
ow f0and the parametric upper bound function
u(i;j;) are indicated.
Considering the feasible
ow f0which is indicated in Figure 1, the residual net-
work~G(f0) for the parametric maximum
ow problem and the residual network
^G(f0) for the parametric minimum
ow problem, with 0= 0 and1= ,
are presented in Figure 2. The residual capacity of every arc is written as
~r(i;j;) = ~(i;j) +
~(i;j). Here, ~(i;j) =~r(i;j; 0) and ~(i;j) =U(i;j).
In the parametric residual network~G(f0), (see. Figure 2.A) the directed path
~P= (0;1;3) is built with the parametric residual capacity ~r0(~P) = 1 + 4, i.e.
~0(~P) = 1 and ~0(~P) = 4. Since for the value = 1=2, the parametric residual

14 Mircea Parpalea
Figure 2: A. The residual network~G(f0) for the parametric maximum
ow problem; B. The
residual network^G(f0) for the parametric minimum
ow problem.
capacity ~r0(~P) = 1 + 4of the directed path crosses the parametric residual ca-
pacity ~r0(1;3;) of the arc (1 ;3) and this parameter value respects the restriction
, the upper limit of the subinterval of the parameter values is updated to
1:== 1=2.
Figure 3: The parametric maximum
ow for each of the subintervals Jk,k= 0;1;2;3 of the
parameter values: (a) J0= [0;1=4]; (b)J1= [1=4;1=2]; (c)J2= [1=2;3=4]; (d)J3= [3=4;1].
In the next step, the parametric residual network~G0(f0) is updated, i.e. the val-
ues ~0(i;j) and ~0(i;j) are updated for both the arcs (1 ;3) and (0;1). Afterwards,
in a similar way, the new directed path~P= (0;2;3) is built and the value of 1
is updated to 1:== 1=41=2. Since at this stage no other directed path

Parametric
ows in static networks 15
can be found, the maximum parametric
ow~f0is computed for the parameter
values in the subinterval J0= [0;1] = [0;1=4] (see Figure 3.a) and the value of
the counter is incremented to k:= 1.
Because16= , the algorithm reiterates within the new interval [1 =4;1]. Af-
ter performing three more iterations, the algorithm ends with the parametric
maximum
ow~fk, separately computed for the subintervals J1= [1=4;1=2],
J2= [1=2;3=4],J3= [3=4;1], as shown in Figures 3.b, c and d.
Figure 4: The parametric minimum
ow for each of the subintervals Jk,k= 0;1;2;3 of the
parameter values: (a) J0= [0;1=3]; (b)J1= [1=3;1=2]; (c)J2= [1=2;4=5]; (d)J3= [4=5;1].
Now, considering the lower bounds of the parametric network in Figure 1 and
the corresponding residual network for the parametric minimum
ow, a similar
algorithm is executed for computing a parametric minimum
ow.
In the parametric residual network^G(f0), (see. Figure 2.B) the directed path
^P= (0;1;3) is built with the parametric residual capacity ^r0(^P) = 1 +. For
the value= 1=3, the parametric residual capacity ^r0(^P) = 1 +of the di-
rected path crosses the parametric residual capacity ^r0(1;3;) of the arc (1 ;3).
The computed value of the parameter respects the restriction  and con-
sequently, the upper limit of the subinterval of the parameter values is updated
to1:== 1=3. According to the parametric residual capacity ^r0(^P), the
residual network^G0(f0) is updated for both the arcs (1 ;3) and (0;1). Then, in a
similar way, the new directed path^P= (0;2;3) is built and the value = 4=7
is found but because the restriction 1i.e. 4=71=3 does not hold, the
value1= 1=3 is maintained. Since at this stage no other directed path can
be found, the minimum parametric
ow^f0is computed for the parameter values

16 Mircea Parpalea
in the subinterval J0= [0;1] = [0;1=3] (see Figure 4.a) and the value of the
counter is incremented to k:= 1.
Figure 5: The piecewise linear maximum ( ~v()) and minimum ( ^v())
ow value functions for
the considered parametric network G= (N;A; `;u;s;t ).
For the new subinterval 16= , the algorithm reiterates within the new interval
[1=3;1]. The directed paths^P= (0;1;3),^P= (0;1;2;3) and^P= (0;2;3) are
consecutively built and parameter value 2is updated to the value = 1=2. For
the the subinterval J1= [1;2] = [1=3;1=2] the minimum parametric
ow^f1is
computed (see Figure 4.b) and the value of the counter is incremented to k:= 2.
After performing two more iterations, the algorithm ends with the parametric
minimum
ow^fk, separately computed for the subintervals J2= [1=2;4=5] and
J3= [4=5;1], as shown in Figures 4.c and d.
The piecewise linear
ow value function  v(), computed according to equation
(12), is presented Figure 5, both for the parametric maximum
ow~f, denoted by
~v(), and for the parametric minimum
ow^f, denoted by ^v(). These
ow value
functions have been computed for the parametric network G= (N;A; `;u;s;t )

Parametric
ows in static networks 17
shown in Figure 1 for the whole range of values of the parameter 2[0;]. As it
can be easily seen, even if for some of the parameter values the functions  v() do
not change their slopes, the parametric maximum or minimum
ows distribute
dierently over the network arcs.
References
[1] Ahuja,R.K., Magnanti,T., Orlin,J.B., Network Flows. Theory, algorithms and appli-
cations , Prentice Hall, Inc., Englewood Clis, New Jersey, 1993
[2] Ahuja,R.K., Orlin,J.B., Stein,C., Tarjan,R.E., Improved algorithms for bipartite net-
work
ow , SIAM Journal on Computing 23(1994), No.5, 906-933
[3] Ahuja,R.K., Orlin,J.B., Distance-Directed Augmenting Path Algorithms for Maxi-
mum Flow and Parametric Maximum Flow Problems , Naval Research Logistics, 38
(1990), 413-430
[4] Bichot,C-E., Siarry,P., Graph Partitioning: Optimisation and Applications , ISTE {
Wiley, 2011
[5] Balinski,M.L., On a selection problem , Management Science 17(1970), No.3,
230{231
[6] Ciurea,E., Parpalea,M., A sequential algorithm for nding the solution of the para-
metric minimum
ow problem , Carpathian Journal of Mathematics 28(2012), No.1,
47-58
[7] Ciurea,E., Parpalea,M., Shortest conditional decreasing path algorithm for the para-
metric minimum
ow problem , Bulletin Math ematique de la Soci et e des Sciences
Math ematiques de Roumanie, 56(104) (2013), No.4, 387-401
[8] Ciurea,E., Parpalea,M., \Balancing Algorithm for the Minimum Flow Problem
in Parametric Bipartite Networks" in: Latest Trends on Computers (vol.I) , 14th
WSEAS International Conference on Computers (part of the 14th WSEAS CSCC
Multiconference), Corfu Island, Greece (2010) 226-231
[9] Eisner,M.J., Severance,D.G., Mathematical techniques for ecient record segmenta-
tion in large shared databases , J. ACM 23(1976), No.4, 619{635
[10] Gallo,G., Grigoriadis,M.D., Tarjan,R.E., A fast parametric maximum
ow algorithm
and applications , SIAM Journal of Computing 18(1989), No.1, 30{55
[11] Goldberg,A.V., Rao,S., Beyond the
ow decomposition barrier , J. ACM 45(1989),
No.5, 783{797
[12] Goldberg,A.V., Tarjan,R.E., A new approach to the maximum-
ow problem , J.ACM
35(1988), No.4, 921{940
[13] Hamacher,H.W., Foulds,L.R., Algorithms for
ows with parametric capacities , ZOR-
Methods and Models of Operations Research 33(1989) 21-37

18 Mircea Parpalea
[14] Hochbaum,D.S., \The Pseudo
ow Algorithm and the Pseudo
ow-Based Simplex
for the Maximum Flow Problem" in: Bixby,R.E., Boyd,E.A., Rios-Mercado,R.Z.
(eds.) Integer Programming and Combinatorial Optimization , LNCS 1412 , Springer,
Heidelberg (1998), 325{337
[15] King,V., Rao,S., Tarjan,R.E., A Faster Deterministic Maximum Flow Algorithm ,
J.Algorithms 17(1994), 447{474
[16] Mamer,J., Smith,S., Optimizing eld repair kits based on job completion rate , Man-
agement Science 28(1982), No.11, 1328{1333
[17] Parpalea,M., Ciurea,E., Minimum Parametric Flow{A Partitioning Approach ,
British Journal of Applied Science & Technology 13(2015), Issue.6, 1-8
[18] Parpalea,M., Ciurea,E., Partitioning Algorithm for the Parametric Maximum Flow ,
Applied Mathematics 4(2013), Special Issue on Computer Mathematics, No.10A,
3-10
[19] Parpalea,M., Min-Max Algorithm for the Parametric Flow Problem , Bulletin of
the Transilvania University of Bra sov 3(52) , Series III: Mathematics, Informatics,
Physics, (2010) 191-198.
[20] Rhys,J.M.W., A selection problem of shared xed costs and network
ows , Manage-
ment Science 17(3), 200{207 (1970)
[21] Ruhe,G., Characterization of all optimal solutions and parametric maximal
ows in
networks , Optimization, 16(1), 51-61, 1985.
[22] Ruhe,G., Complexity results for multicriterial and parametric network
ows using a
pathological graph of Zadeh , Zeitschrift f ur Operations Research, 32, 9-27, 1988.
[23] Tarjan,R.E., Ward,J., Zhang,B., Zhou,Y., Mao,J., \Balancing Applied to Maximum
Network Flow Problems" in: Azar,Y., Erlebach,T. (eds.) European Symposium of
Algorithms 2006 , Lecture Notes in Computer Science 4168 (2016), Springer, Berlin,
Heidelberg, 612{623
[24] Zhang,B., A new balancing method for solving parametric maximum
ow problems ,
Stanford EE, Computer Systems Colloquium, 2007
[25] Zhang,B., Ward,J., Feng,Q., A simultaneous parametric maximum
ow algorithm
with vertex balancing , Technical Report HPL-2005-121, HP Labs, 2005