Relabel-to-Front Algorithm: Maximizing Network Flow

Understand the Relabel-to-Front algorithm, an efficient method for finding the maximum flow in a network. Learn how push and relabel operations work together to optimize flow calculations and improve upon the basic push-relabel algorithm.

Relabel-to-Front Algorithm

Introduction

The relabel-to-front algorithm is used to determine the maximum flow in a network. It improves upon the generic push-relabel algorithm by carefully selecting the order of operations and efficiently managing network data structures. This makes it more effective than the basic push-relabel approach.

Basic Operations: Push and Relabel

  • Push: When a vertex has excess flow and an adjacent node in the residual graph has a lower height, the flow is pushed from the vertex to the node with the lower height.
  • Relabel: If a vertex has excess flow but no neighboring nodes with a lower height, the vertex is "relabelled" to a taller height, enabling further push operations.

Algorithm Steps

  1. Initialize the preflow and heights of all vertices.
  2. Create a list L containing all vertices except the source and sink.
  3. Set the current pointer of each vertex to the first vertex in its neighbor list N, which includes all vertices with residual edges.
  4. While traversing list L:
    • Pick a vertex u from the list and perform a discharge operation.
    • If u is relabeled during discharge, move it to the front of the list.
    • If u is moved to the front, continue with the next vertex in the updated list order.

The algorithm ends when no vertex in the list has positive excess flow. At this point, the maximum flow is reached.

Example

Consider a flow network with the following initial setup:

  • Initial list: L = (B, C).
  • Starting vertex: u = B.

Step-by-Step Execution

  1. Vertex B has an excess flow of 3 (e = 3).
    • Performs a relabel operation (h = 1).
    • Pushes flow 1 to vertex C.
  2. Vertex B still has excess flow 2 (e = 2).
    • Performs another relabel operation (h = 5).
    • Pushes flow 2 to vertex A.
  3. Vertex C now has excess flow 1 (e = 1).
    • Performs a relabel operation (h = 1).
    • Pushes flow 1 to node D.
    • Moves to the front of the list as it performed a relabel operation.
  4. Vertex B follows vertex C but no longer has excess flow. The algorithm terminates when all vertices in L are processed.

At this point, the maximum preflow is achieved, and the maximum flow is 1.

Time Complexity

The relabel-to-front algorithm runs in O(V³) time on a network G with V vertices and E edges. It performs better than the generic push-relabel algorithm, which has a time complexity of O(V²E).