Introduction to Algorithms, Third Edition

Exercises
26.5-1
Illustrate the execution of R
ELABEL
-T
O
-F
RONT
in the manner of Figure 26.10 for
the flow network in Figure 26.1(a). Assume that the initial ordering of vertices in
L
is
h
1
; 
2
; 
3
; 
4
i
and that the neighbor lists are
1
:
N
D h
s; 
2
; 
3
i
;
2
:
N
D h
s; 
1
; 
3
; 
4
i
;
3
:
N
D h
1
; 
2
; 
4
; t
i
;
4
:
N
D h
2
; 
3
; t
i
:
26.5-2
?
We would like to implement a push-relabel algorithm in which we maintain a first-
in, first-out queue of overflowing vertices. The algorithm repeatedly discharges the
vertex at the head of the queue, and any vertices that were not overflowing before
the discharge but are overflowing afterward are placed at the end of the queue.
After the vertex at the head of the queue is discharged, it is removed. When the

---

760
Chapter 26
Maximum Flow
queue is empty, the algorithm terminates. Show how to implement this algorithm
to compute a maximum flow in
O.V
3
/
time.
26.5-3
Show that the generic algorithm still works if R
ELABEL
updates
u:
h
by sim-
ply computing
u:
h
D
u:
h
C
1
. How would this change affect the analysis of
R
ELABEL
-T
O
-F
RONT
?
26.5-4
?
Show that if we always discharge a highest overflowing vertex, we can make the
push-relabel method run in
O.V
3
/
time.
26.5-5
Suppose that at some point in the execution of a push-relabel algorithm, there exists
an integer
0 < k
j
V
j 
1
for which no vertex has
:
h
D
k
. Show that all
vertices with
:
h
> k
are on the source side of a minimum cut. If such a
k
exists,
the
gap heuristic
updates every vertex
2
V
f
s
g
for which
:
h
> k
, to set
:
h
D
max
.:
h
;
j
V
j C
1/
. Show that the resulting attribute
h
is a height function.
(The gap heuristic is crucial in making implementations of the push-relabel method
perform well in practice.)