Questions tagged [network-flow]

For questions related to the formulation or solution methodologies of network flow problems. Some of the well-known network flow problems are maximum flow problem, minimum-cost flow problem, and multi-commodity flow problem.

Filter by
Sorted by
Tagged with
17 votes
1 answer

Was there something specific that caused graph cuts to lose popularity in the last 5 years?

Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago: For privacy I've cut the all ...
Nike Dattani's user avatar
  • 1,268
6 votes
1 answer

Complexity \ Reference request for variant of max flow problem

In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the ...
batwing's user avatar
  • 1,458
5 votes
4 answers

How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
bsha's user avatar
  • 81
3 votes
1 answer

Reformulating undirected to directed edges for MCF

As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges. By quoting them: The ...
Daniele Cuomo's user avatar
2 votes
2 answers

Min cut network for patients

I'm trying to formulate a min cut algorithm There are two classes of patients: 1, 2, and the maximum number of patients that can be assigned to each bed per day is shown below as well. $$ \begin{array}...
Devita J's user avatar