This is an old revision of the document!
Table of Contents
7.7 Extensions to the Maximum-Flow Problem
The Problem: Circulations with Demands
- Directed graph G = (V, E)
- Edge capacities c(e), e ∈ E
- Node supply and demands d(v), v ∈ V:
- If d(v) > 0: node v has demand of d(v) flow–> The node is a sink and wishes to receive d(v) units more flow than it sends out
- If d(v) < 0: The node v has a supply of -d(v)–> The node is a source and wishes to send out -d(v) units more flow than it receives
- If d(v) = 0: Then the node is neither a source nor a sink.
- A circulation is a function that satisfies:
- For each e ∈ E: 0 ≤ f(e) ≤ c(e) (capacity condition)
- For each v ∈ V: fin(v) - fout(v) = d(v)(Demand conditions)
- Feasibility Problem: We want to know if there exists a circulation that satisfies the just-mentioned conditions
- If there exists a feasible circulation with demands {d(v)}, then ∑v d(v) =0
Designing And Analyzing an Algorithm for Circulations
- The problem of finding feasible circulation can be reduced to the problem of finding a maximum s-t flow in a different network.
