0
$\begingroup$

I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section

Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex has a limit $l$ on how much flow can pass though . Show how to transform a flow network $G = (V, E)$ with vertex capacities into an equivalent flow network $G' = (V', E')$ without vertex capacities, such that a maximum flow in $G'$ has the same value as a maximum flow in $G$.

I want to understand how the author has defined vertex capacities here? Because from my understanding, the most general definition would be

$l(v) = \sum\limits_{e \text{ into } v} f(v) - \sum\limits_{e \text{ out of } v} f(v)$

but if this is so, then for all $v$ not in the set of source and sink nodes,

$l(v)= 0$, so we are never really setting any limit. Please help me understand the vertex capacity term.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Just like edges have capacities on them (i.e, how much flow is allowed to go through them), they have added capacities for nodes.

If a node $v$ has capacity $C_v$, then any flow with $\sum_{e \text{ into } v} f(e)>C_v$ is considered invalid (it violates the node capacity rule).

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, we are putting an upper bound on the flow that can go into a vertex when we talk about network capacity. Would that be correct interpretation? $\endgroup$
    – chesslad
    Commented Nov 16, 2021 at 15:15
  • $\begingroup$ Yes, exactly. Intuitively it is the same definition like for capacity in edges. $\endgroup$
    – nir shahar
    Commented Nov 16, 2021 at 15:32
  • $\begingroup$ Thank you so much for clarifying it for me. I'm unable to upvote because I don't have the necessary reputation. Thank you so much. $\endgroup$
    – chesslad
    Commented Nov 16, 2021 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.