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?