JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial Balanced maxflow
 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
 Forums Tutorial Discussions Maximum Flow tutorial Balanced maxflow Previous Thread  |  Next Thread