Trivia ForgePlay free →

In the push-relabel algorithm for maximum flow, what is the term for a flow function that satisfies capacity constraints but allows the net flow into a vertex to exceed the net flow out?

Show answer

Pre-flow

Unlike Ford-Fulkerson, push-relabel algorithms do not maintain the flow conservation property during execution. Instead, they allow nodes to have an 'excess' flow (overflow) that is eventually pushed to the sink or back to the source.

Also asked as:
  • In maximum flow problems, what term describes a flow function that satisfies capacity constraints but may violate flow conservation by allowing more flow in than out?

Would you remember this in 6 months?

Trivia Forge uses spaced repetition so facts stick. Free, no signup needed.

Turn on Algorithms practice →

More Algorithms trivia

See all 83 →