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.
6
questions
17
votes
1
answer
362
views
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 ...
- 1,278
5
votes
4
answers
1k
views
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 ...
- 81
6
votes
1
answer
105
views
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 ...
- 1,583
5
votes
1
answer
307
views
How to model this multi-commodity flow problem with a twist?
Problem description
I am working on a variation of the multicommodity flow problem on a graph $G=(V,E)$. I have requests $r_{uv}$ for pairs of nodes $(u,v), u\in V, v\in V$, which means that $r_{uv}$ ...
- 13.7k
3
votes
1
answer
91
views
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 ...
- 571
2
votes
2
answers
218
views
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}...
- 67