Augmenting flows and refinements Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
13 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 13 cards
- What is a flow-augmenting route?
- A route from source to sink along which the flow can be increased, using forward spare capacity and backward flow.
- How do you find the spare capacity of an arc?
- Capacity minus current flow.
- What is the increase along an augmenting route?
- The smallest spare capacity (or backward amount) on the route.
- How can a backward arc be used?
- Travel against the arc's direction to cancel some of its flow, up to the flow currently on it.
- When does the augmenting algorithm stop?
- When no flow-augmenting route from source to sink exists.
- How do you prove the final flow is maximal?
- Find the cut whose arcs are all saturated, show its capacity equals the flow, and quote the max-flow min-cut theorem.
- What does an arc with limits mean?
- The flow on the arc must be at least and at most .
- What is the forward spare capacity on an arc with limits carrying ?
- .
- How much flow can be cancelled backwards on that arc?
- .
- What is the capacity of a cut when arcs have lower capacities?
- Sum of upper capacities of arcs from to , minus sum of lower capacities of arcs from to .
- How do you model a node with restricted capacity?
- Split it into two nodes joined by an arc with the restricted capacity; arcs in go to the first, arcs out leave the second.
- Where do you find the bottleneck in a network?
- In the arcs of a minimum cut.
- When does raising an arc's capacity raise the maximum flow?
- Only if the arc is in every minimum cut, and by no more than the next smallest cut allows.