Haruka's blog

By Haruka, history, 6 months ago, In English

Recently I have read about the Edmonds-Karp algorithm and the solution to the flows with demands problem. Thus, I come up with the following problem but haven't found a solution yet:

Given a directed graph G(V, E) including a source s (no incoming edge) and a sink t (no outgoing edge). Each edge e in E consists of 3 attributes: l(e), u(e), w(e). Find a flow f from s to t such that l(e) <= f(e) <= u(e) for all edges e in E and the sum of w(e)f(e) is maximized?

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it