Chapter 1 Network Flow- COMP 5703 Course Note Update

The Push-Relabel, or Preflow-Push, Maximum-Flow algorithm was originally developed by Andrew V. Goldberg and Robert E. Tarjan in the mid-to-late 1980s, [2, 3]. This Push-Relabel algorithm is unlike the previous Ford-Fulkerson and Edmonds-Karp algorithms which use the concept of an augmenting path to determine the maximum flow. This algorithm instead uses a concept of a preflow, originally developed by A. V. Karzanov [4], in order to determine the maximum flow on a flow network graph G = (V,E), [3]. 1.1.1 Generic Push-Relabel The Push-Relabel algorithm, as described in [3], works by manipulating a preflow of the original flow network. In [3], Goldberg and Tarjan outline a generic version of their Push-Relabel algorithm. This generic algorithm defines the general operations required but does not specify the operation ordering or discusses implementation details. The algorithm works at converting a preflow, f, to a flow by pushing local flow excess starting at the source, s, along the vertices towards the sink, t. To accomplish this, the algorithm maintains a compatible vertex labeling function, d, to the preflow f in order to determine where to push the flow excess. The algorithm terminates once the preflow becomes a flow. This final flow produced at termination also turns out to be the maximum flow for the graph. Preflow is a real-valued function f on vertex pairs wherein the total flow into a vertex can exceed the flow out of the vertex. By definition, preflows must satisfy the capacity constraint, the skew symmetry constraint and the non-negative constraint. A preflow where all v ∈ V − {s, t} have a flow excess of zero, ef (v) = 0, is a normal flow. The preflow function is also referred to as s-t preflow. Non-Negative Constraint is a weakened form of the flow conservation constraint which states 1 that the flow into v ∈ V − {s} must be greater or equal to the total flow out of v.∑ u∈V f(u, v) ≥ 0, ∀v ∈ V − {s} Flow Excess is the net flow into v where v ∈ V for some preflow, f. ef (v) = { ∞, v=s∑ u∈V f(u, v), ∀v ∈ V − {s}