JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Balanced maxflow | Reply
I am looking for an efficient algorithm for balanced maxflow in a digraph. By balanced I mean if there are mutiple paths from source to the sink node, the flow is divided in a balanced across participating edges.
For example consider the graph; G={(a,b,4),(b,c,4),(b,d,4),(c,e,4),(d,e,4) }
In this graph the maxflow from 'a' to 'e' is 4. The balanced maxflow is the one that carries 2 units along the edges (b,c),(b,d),(c,e),(d,e).


R.
Re: Balanced maxflow (response to post by rdelaviz) | Reply
> By balanced I mean if there are mutiple paths from source
> to the sink node, the flow is divided in a balanced across
> participating edges.

That's a rather imprecise definition.

Here's one way to formalize it - find a maximum flow that minimizes the maximum flow through any edge. Does that sound good to you?

You can solve it by binary searching the bound on capacities and running a standard maxflow algorithm at each step of the binary search. It'll find the flow you want on your example.
Re: Balanced maxflow (response to post by kia) | Reply
Hi Kia,

"Here's one way to formalize it-find a maximum flow that minimizes the maximum flow through any edge". Also this formalization is very close but it is not exactly what I mean. Suppose in the example graph we change the capacity of the edges (b,c) and (c,e) to 8. In this the 3 units of flow for these edges and 1 unit for the edges (b,d) and (d,e) seems more balanced, but in yout formulation the answer is 2 for all edges.


But your solution for minimizing the maxflow over each edge seems reasonable ( not sure about its efficiency). Would you elaborate it more, or if you have any reference mention it.

Tnx a lot
RSS