Skip to main content

New answers tagged

1 vote
Accepted

Minimum flow in a flow network

This question has been addressed here. Aparantly, there are algorithms which deals with both minimum and maximum flow capacities. In your case max capacities are unbounded. The details are given in ...
codeR's user avatar
  • 1,283
1 vote

Maximum network flow with few non-integral edges

I think your problem is NP-hard here is why: Given an instance of the Subset-Sum problem $I = (<a_1,a_2,\dots,a_n>, S)$, you can construct a network-flow graph where you have three vertices a ...
codeR's user avatar
  • 1,283
1 vote

Least interrupted max flow after removing K edges algorithm

The paper Finding k most influential edges on flow graphs should show that this is NP-complete and inapproximable. Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T.-H. Hubert ...
Pål GD's user avatar
  • 16.7k
2 votes
Accepted

Least interrupted max flow after removing K edges algorithm

There is a polynomial solution for a case of unit edge capacities. At the same time the problem is NP-hard for arbitrary edge capacities. Suppose that every edge has capacity $1$. Here is a scheme of ...
Smylic's user avatar
  • 303

Top 50 recent answers are included