COMPSCI320 Chap.12 Faster Flow Algorithms and Flow Modelling
Faster Flow Algorithms and Flow Modelling
This chapter fixes the running time of Ford-Fulkerson and turns flow into a modelling tool. Capacity scaling augments only along large-bottleneck paths, the shortest augmenting path rule bounds the number of augmentations by the number of edges times vertices, and Dinitz works one level graph at a time.
The second half builds assignment networks, splits vertices to cap their throughput and states each decision rule.
The figures show capacity scaling's phases on the network from the previous chapter and a layered assignment model, and the practice cards build complete feasibility models with their decision rules.
The practice cards cover vertex limits and disjoint paths, the topics of the fifth programming assignment.
What this chapter covers
- 01
Capacity scaling and its phases
- 02
Shortest augmenting paths and level graphs
- 03
Dinitz's algorithm and unit capacities
- 04
Assignment problems as layered networks
- 05
Vertex splitting for throughput limits
- 06
Feasibility from the flow value
Worked example · free
Capacity scaling phase by phase
- 1Delta = 8: no path uses only residual edges of capacity at least 8, so the phase makes no augmentation.
- 1Delta = 4: augment s, a, t by 4, s, a, c, t by 5 and s, b, c, t by 4, reaching 13.
- 1Delta = 2: augment s, b, t by 2, reaching 15.
- 1Delta = 1: no augmenting path remains, so 15 is the maximum flow.
Key terms
- Capacity Scaling
- A maximum flow method that augments only along paths whose bottleneck is at least a threshold that halves each phase.
- Level Graph
- The subgraph keeping only edges that lead from one breadth-first level to the next.
- Vertex Splitting
- Replacing a vertex by an in-copy and an out-copy joined by one edge whose capacity limits the vertex's throughput.
- Dinitz Algorithm
- A maximum flow method that saturates paths in one breadth-first level graph at a time.
- Shortest Augmenting Path
- A maximum flow rule that always augments along a residual path with the fewest edges.
Faster Flow Algorithms and Flow Modelling FAQ
How many phases does capacity scaling use?
The threshold starts at the largest power of two not exceeding the largest capacity C and halves until it reaches 1, so there are one plus the floor of log base two of C phases. The lecture shows each phase uses at most 2m augmentations, giving a total running time of m squared times log C.
Why split a vertex in a flow model?
Flow networks put capacities on edges, not vertices. When a rule limits how much can pass through an item in total, such as a depot or a cow that can be fed only once, replace the vertex by an in-copy and an out-copy joined by a single edge with that limit. All flow through the item must then cross that edge.
What makes a flow model complete in an exam answer?
Four things: the vertex set, every edge with its capacity, the decision rule linking the maximum flow to the question, and a running time for the chosen algorithm on the network's size. Without the decision rule the model answers nothing, because a flow value on its own does not say whether the assignment exists.
How does maximum flow count disjoint paths?
Give every edge capacity one. An integral flow of value k then splits into k paths that share no edge, and any k edge-disjoint paths give a flow of value k. For paths that may not share vertices, split every intermediate vertex into an in-copy and an out-copy joined by an edge of capacity one first.
Exam move
Trace capacity scaling on the Chapter 11 network phase by phase, then compare its phase count with the plain augmentation count. For modelling, rewrite three story problems as networks, drawing a tiny instance of each first, and finish each with its decision rule and running time. For the exam, prepare one model of each kind, an assignment, a vertex limit and a disjoint-path count, so you can adapt a known structure quickly.
Compare the bounds of the methods in a single table and say which one depends on the capacities.
Working through Faster Flow Algorithms and Flow Modelling in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Faster Flow Algorithms and Flow Modelling question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
