Consider an undirected weighted graph G with all edges of equal capacity. For each pair of its vertices I need to find the set of paths, which corresponds to max flow of minimal cost between these vertices.

The naive approach is to use some min-cost max-flow algorithm for each pair of vertices, which gives us about o(n^2 * T(min-cost max-flow)). Is there any way to reduce the complexity?

It is also possible to find all min cut (and max-flow) values by constructing Gomory-Hu tree. But I am not sure, if known min cuts can help to reconstruct the corresponding paths.

  • 2
    $\begingroup$ I get confused when two objective functions are being optimized at the same time. You mention that the edges are of equal capacity, so presumably the undirected graph $G$ gives us the information we need to determine maximum flow from one specified source node to another specified sink node. You also mention that the graph is "weighted", which may have something to do with your notion of cost. However it leaves the nature of the cost calculation open to interpretation. Is there some clarification you can provide about the cost model and the order of optimizations? $\endgroup$ – hardmath Jun 19 '17 at 12:51
  • 1
    $\begingroup$ @hardmath, sorry for inaccurate formulation. The goal is to find maximum flow value in terms of capacity first, and select a set of paths, which reaches this value, while involving edges with the lowest possible total weight, second. $\endgroup$ – eugene_che Jun 19 '17 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.