3
$\begingroup$

I am facing a hard time understanding Blocking Flow problem. This is what I have understood till now : We have a graph and in blocking flow problem we find all shortest paths from source to destination and saturate atleast one edge in all of the shortest paths respectively [1] and we delete that path. In examples I am reading online, it is explained with an example of graph with all edges of unit length [2]. Our professor explained the solution to this using dynamic trees. I am unable to apply the concept of dynamic trees (splay) for the solution of this problem. What will be stored in the nodes of the tree and on what basis will we perform the spaly operation?

[1] There can only be one shortest path, or many shortest paths of same length. What is the concept of all shortest paths?

[2] If a graph has all edges of unit lengths, then all the edges will be deleted (because all will appear in some path from source to sink). Then, source and destination will be disconnected in the end. What would be the use of doing this?

What is the goal for solving this problem? Can someone point in right direction in layman's terms? Also I have read some articles regarding this but unable to understand them and also none of them uses splay trees to solve this problem.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You can't explain a problem by sketching an algorithm for solving it. What are inputs and desired outputs? That would specify the problem. $\endgroup$
    – Raphael
    Commented Sep 24, 2016 at 21:31
  • $\begingroup$ The desired input is a network, let's say we need to lay train tracks, then what would be a blocking flow in such a rail network? $\endgroup$
    – Mojo Jojo
    Commented Sep 24, 2016 at 21:52
  • 3
    $\begingroup$ You are asking several different questions. I answered only the one in the title. Any other questions should be asked separately, per community norms. $\endgroup$
    – Yuval Filmus
    Commented Sep 25, 2016 at 0:28

1 Answer 1

Reset to default
4
$\begingroup$

A blocking $s$-$t$ flow is a flow whose residual network (consisting of all edges not saturated by the flow) contains no $s$-$t$ path. Stated differently, a blocking flow is a flow which, for every $s$-$t$ path, saturates at least one edge. Equivalently, a blocking flow is a flow which, for every simple $s$-$t$ path, saturates at least one edge.

The blocking flow problem is to find a blocking flow in a flow network. Such a flow exists since a maximum flow is always a blocking flow (but not vice versa).

The concept of blocking flow is used in Dinitz's maximum flow algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for explaining. Now if I have got my blocking flow in my graph, then what are its practical implications? Is our goal is to disconnect $s$ and $t$ ? Won't that be easy by just deleting all the outgoing edges from $s$ ? $\endgroup$
    – Mojo Jojo
    Commented Sep 25, 2016 at 4:30
  • $\begingroup$ The concept is used in Dinitz's algorithm. That's where it comes from. $\endgroup$
    – Yuval Filmus
    Commented Sep 25, 2016 at 4:31

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.