liveBook · Manning

Chapter 10: Push Relabel Algorithm

What you will learn in chapter 10 of Algorithms Every Programmer Should Know

Introduces maximum network flow as a capacity problem and motivates Push-Relabel’s local approach over repeated global path searches.

After this chapter you will be able to

What it builds on

Section by section

Introduction

Introduces maximum network flow as a capacity problem and motivates Push-Relabel’s local approach over repeated global path searches.

Key terms: maximum flow, carrying capacities, source, sink, global augmenting paths, Push-Relabel algorithm, localized

10.1 The mechanics of maximum network flow

The section traces push-relabel on a four-node network, showing how temporary excess, local pushes, relabeling, and reverse residual edges produce a maximum flow without repeated end-to-end path searches.

Key terms: preflow, excess, conservation of flow, local decisions, source height, saturate, active node, residual capacity, height, push

10.2 Real-world applications

The section shows how maximum flow is used to test baseball elimination, plan profitable open-pit mines, and power graph-library backends.

Key terms: game-pair node, maximum flow, W − wᵢ, eliminated, structural monotonicity property, maximum achievable win totals, open pit mining, ultimate-pit-limit design, net economic value, positive-profit block

10.3 Key Insights

This section summarizes Push–Relabel’s complexity, local-flow design, termination argument, minimum-cut interpretation, and active-node scheduling choices.

Key terms: time complexity, highest-label selection heuristic, space complexity, adjacency lists, local node relaxation, residual graph, excess flow, global conservation constraints, heights, relabel operations

10.4 Summary

10.5 References

This section lists external references for Push–Relabel implementations, explanations, applications, and library documentation.

Where this is used later

Concepts explained in this chapter

← Chapter 9: Floyd-Warshall Algorithm Chapter 11: Bron-Kerbosch Algorithm →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.