In a standard s - t maximum flow problem, we assume edges have capacities, and there is no limit on how much flow is allowed to flow through a node.
In this problem, we consider the variant of the maximum flow and minimum cut problems with node capacities. Let G = (V, E) be a directed graph, with source s, sink t , and non-negative node capacities uv for each v ? V .
Given a flow f in this graph, the flow though a node v is defined as P e?d-(v) fe. where d -(v) denotes the edges coming into v. We say that a flow is feasible, if it satisfies the usual flow-conservation constraints and the node-capacity constraint: the flow through a node v cannot exceed cv.
Give a polynomial-time algorithm to find a s - t maximum flow in such node-capacitated network.
Define an s - t cut for node-capacitated networks, and show that the analog of the Maximum Flow Min Cut theorem holds true.