tag

#network-flow

26 pages tagged

Programming › Algorithm Cookbook ›

Chapter 12. Network Flow and Matching

Chapter 12. Network Flow and Matching
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.6 Push-Relabel Algorithm

12.6 Push-Relabel Algorithm Problem The algorithms developed so far share a common strategy. They search for augmenting paths from the source to the sink and then push additional flow along those paths. This approach works well, but it has an important limitation. Every augmentation requires discovering a complete path through the residual network before any progress can be made. In large networks, repeatedly searching for source-to-sink paths can become expensive....
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.16 Vertex Capacities

12.16 Vertex Capacities Problem Standard flow networks place capacity constraints on edges. That works when the limiting resource is a road, pipe, cable, route, or connection. But in many problems, the bottleneck belongs to a vertex. Examples: A warehouse can process at most 500 packages per hour. A router can forward at most 10 Gbps. A machine can handle at most 12 jobs. A hospital can admit at most 40...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.15 Lower Bounds on Edges

12.15 Lower Bounds on Edges Problem A normal flow edge has only an upper capacity: 0 ≤ f(u, v) ≤ c(u, v) Many practical models need a minimum commitment as well. A truck route may need at least 3 shipments per day to justify operating. A contract may require a supplier to deliver at least 100 units. A shift may require a minimum staffing level. A network reservation may require...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.1 Flow Networks

12.1 Flow Networks Problem You need to model the movement of resources through a constrained system. The resources may represent data packets, water, vehicles, products, workers, money, electricity, or any quantity that moves between locations. Each connection has a limited capacity, and the objective is to determine how much can be transported from a source to a destination while respecting all constraints. Examples include: Delivering products from warehouses to stores...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.20 Image Segmentation with Graph Cuts

12.20 Image Segmentation with Graph Cuts Problem Suppose you have an image and want to separate the foreground from the background. Examples include: Removing a background from a photograph Identifying tumors in medical images Detecting roads in satellite imagery Isolating objects in computer vision systems Separating products from backgrounds in e-commerce photos At first glance, image segmentation appears completely unrelated to network flow. An image consists of pixels. Maximum flow...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.12 Hungarian Algorithm

12.12 Hungarian Algorithm Problem You need to solve an assignment problem exactly. There are n workers and n tasks. Each worker can be assigned to exactly one task, and each task can be assigned to exactly one worker. Every worker-task pair has a cost. The goal is to minimize total cost. Example: Worker Job A Job B Job C Alice 8 2 7 Bob 6 4 3 Carol 5 8...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.4 Edmonds-Karp Algorithm

12.4 Edmonds-Karp Algorithm Problem The Ford-Fulkerson method provides a simple framework for computing maximum flow, but its performance depends heavily on the choice of augmenting paths. Different path selections can lead to dramatically different running times. Consider a network where one path increases flow by 100 units while another increases flow by only 1 unit. A poor path selection strategy may require thousands of augmentations before reaching the optimum. Even...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.18 Vertex-Disjoint Paths

12.18 Vertex-Disjoint Paths Problem Edge-disjoint paths are allowed to share vertices. In some applications, that is not enough. Consider two communication routes: s -> A -> C -> t s -> B -> C -> t These paths do not share their first edges, but both depend on vertex C . If C is a router, checkpoint, warehouse, switch, bridge, or processing station, then C is still a single point...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.21 Scheduling Applications

12.21 Scheduling Applications Problem Scheduling problems often look different from flow problems. You may need to assign: Workers to shifts Jobs to machines Students to exams Nurses to hospital wards Deliveries to time windows Courses to rooms Tasks to processors Each assignment must respect constraints: availability, capacity, minimum coverage, maximum workload, skill requirements, time windows, and sometimes fairness rules. The challenge is to recognize when a scheduling problem is really...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.11 Assignment Problem

12.11 Assignment Problem Problem In maximum bipartite matching, every assignment has the same value. The goal is simply to maximize the number of matches. Many real-world allocation problems are more complicated. Every assignment has a cost, profit, distance, or score. Consider assigning workers to jobs: Worker Job A Job B Job C Alice 8 2 7 Bob 6 4 3 Carol 5 8 1 The numbers may represent: Time required...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.8 Max-Flow Min-Cut Theorem

12.8 Max-Flow Min-Cut Theorem Problem A maximum-flow algorithm returns a number. That number tells you how much flow can be sent from the source to the sink. But an algorithmic answer alone is not enough. You also need a reason why the answer is optimal. Suppose an algorithm returns: maximum flow = 37 How do you know that 38 is impossible? A minimum cut provides the certificate. The max-flow min-cut...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.23 Complexity Analysis

12.23 Complexity Analysis Problem Flow algorithms solve the same abstract problem, but their running times differ sharply. A small network can be solved with almost any implementation. A large scheduling system, matching engine, or transportation model may require careful algorithm selection. The wrong choice can turn a feasible computation into an unusable one. You need a way to compare flow algorithms by graph size, capacity size, density, and problem structure....
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.7 Minimum Cut

12.7 Minimum Cut Problem Maximum flow asks how much can be sent from a source to a sink. Minimum cut asks a complementary question: what is the smallest amount of capacity that must be removed to separate the source from the sink? At first these sound like different problems. One measures throughput. The other measures vulnerability. In a transportation network, maximum flow tells you how many trucks can move from...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.3 Ford-Fulkerson Algorithm

12.3 Ford-Fulkerson Algorithm Problem Given a flow network with capacities on every edge, determine the maximum amount of flow that can be sent from the source to the sink. For small networks, it is often possible to find a solution manually. For larger networks, the number of possible flow assignments becomes enormous. Exhaustively searching all assignments quickly becomes impractical. We need a systematic method that starts from an empty flow...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.5 Dinic's Algorithm

12.5 Dinic's Algorithm Problem Edmonds-Karp guarantees polynomial running time, but it still performs only one augmentation per BFS search. Consider a network containing thousands of shortest augmenting paths. Edmonds-Karp may discover: Path 1 augment Path 2 augment Path 3 augment ... even though all paths belong to the same shortest-path structure. The repeated BFS traversals become expensive. We need an algorithm that can exploit many shortest augmenting paths at once....
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.14 Circulation with Demands

12.14 Circulation with Demands Problem So far, flow networks have had a source and a sink. Flow starts at s , moves through the graph, and ends at t . Many real systems are not organized that way. A supply network may contain several producers and several consumers. A transportation system may require certain minimum shipments on specific routes. A scheduling model may require every department to receive a fixed...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.22 Correctness Proofs

12.22 Correctness Proofs Problem Flow algorithms are easy to implement incorrectly because their state changes over time. Residual capacities change. Reverse edges appear. Flow may be pushed forward, canceled backward, or rerouted through a different path. A program can return a plausible number while violating conservation, exceeding capacity, or stopping too early. A correctness proof gives you a disciplined way to reason about the algorithm: What is preserved after every...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.19 Project Selection

12.19 Project Selection Problem You have a set of possible projects. Each project has a profit or a cost. Some projects depend on other projects. Example: Project Value Build API +10 Build Database Layer -4 Build Auth -3 Build Dashboard +8 Dependencies: Build API requires Build Database Layer Build Dashboard requires Build API Build Dashboard requires Build Auth You want to choose a subset of projects that maximizes total value...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.10 Hopcroft-Karp Algorithm

12.10 Hopcroft-Karp Algorithm Problem You need to find a maximum matching in a bipartite graph. A generic max-flow algorithm works, but bipartite matching has extra structure. Every augmenting path alternates between unmatched and matched edges. Instead of finding one augmenting path at a time, we can find many shortest augmenting paths in phases. This is the same performance idea used by Dinic: build layers, then augment through many disjoint paths...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.9 Bipartite Matching

12.9 Bipartite Matching Problem Suppose you have a set of workers and a set of tasks. Each worker can perform only certain tasks. Worker Tasks Alice A, B Bob B, C Carol A, C You want to assign as many workers as possible such that: Each worker receives at most one task. Each task is assigned to at most one worker. This problem appears in many domains: Job assignment Course...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.13 Minimum-Cost Maximum-Flow

12.13 Minimum-Cost Maximum-Flow Problem Traditional maximum-flow algorithms answer a single question: How much flow can be sent from the source to the sink? They do not care where that flow travels. Consider the network: cost=1 A ----------> T / S \\n B ----------> T cost=10 Both paths have capacity: 10 A maximum-flow algorithm sees no difference between them. However, in practice the paths may represent: Transportation routes Communication links Manufacturing...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.25 Common Flow Modeling Patterns

12.25 Common Flow Modeling Patterns Problem Many optimization problems appear completely different on the surface. Consider these examples: Assign nurses to hospital shifts. Match students to courses. Route packages through warehouses. Allocate cloud resources to applications. Schedule manufacturing jobs. Select profitable projects. Segment an image. Verify network reliability. The problem statements use different terminology and come from different domains. Yet experienced algorithm designers often solve all of them with network...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.2 Residual Graphs

12.2 Residual Graphs Problem Suppose you have already constructed a valid flow in a network. You discover another path from the source to the sink and want to increase the total flow. A natural approach is to send additional flow through the newly discovered path. Unfortunately, previous decisions may block better solutions. Consider the network: Edge Capacity S → A 10 S → B 10 A → B 5 A...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.17 Edge-Disjoint Paths

12.17 Edge-Disjoint Paths Problem Suppose you are designing a communication network between two data centers. A single path between the source and destination may be sufficient under normal conditions. But if one cable fails, communication stops. A more reliable design uses multiple independent routes. Example: s -> A -> t s -> B -> t s -> C -> t Even if one route fails, traffic can continue using the...
algorithms graphs network-flow Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.24 Testing Flow Code

12.24 Testing Flow Code Problem Flow implementations are compact, but bugs are easy to hide. A wrong residual update may still return a plausible value on small examples. A missing reverse edge may pass tests where no rerouting is needed. A sign error in lower-bound circulation may work on balanced toy inputs and fail on real cases. Flow code needs tests that check both the final answer and the internal...
algorithms graphs network-flow Jun 1, 2026