# Questions tagged [network-flow]

For questions about networks that inhibit source and sink nodes and a notion of flow.

262 questions
0answers
12 views

### Dinic's algorithm

Given $N = (G = (V , E),s, t, c)$ a flow network, we run the Dinic's algorithm (https://en.wikipedia.org/wiki/Dinic%27s_algorithm) on this Network. Consider some iteration $i$ which is not the last ...
1answer
24 views

### Cut In a Flow Network

Given $N = (G = (V , E),s, t, c)$ a flow network (assume that the capacity $c$ is always positive) and $e = (u,v) \in E$. I would like to develop an algorithm that tell if there exist a min-cut (cut ...
1answer
16 views

### How to find the vertices of one component in a min-cut problem?

I need to write a min-cut algorithm on a undirected graph, and retrieve the vertices of one of the components $S$ or $T$. I know some algorithms, like resolving the associated Max Flow problem or ...
1answer
19 views

1answer
83 views

### Min cost flow change in objective function by changing flow of some arc

I solving a problem that is formulated as a min cost flow problem. After finding the optimal solution, I would like to determine how the objective function will change if I increase/decrease flow of ...
0answers
134 views

### Example of a Minimum Cost Capacitated Flow Problem

I am struggling to find an example with a solution for a Minimum Cost Capacitated Flow problem. My network is defined as a graph G = (V, E), where each edge has a capacity c(u, v) > 0, a flow f(u, v) ...
0answers
12 views

### Graph with every node a binary flow of 1 out of every node

Is there a name for this type of graph? I have a hypergraph and am wondering if there is a name for when we have a flow of exactly one out of each node, along only one edge. There can be any amount of ...
0answers
83 views

### Maximum double-matching problem in a bipartite graph using max-flow algorithm

Ive encountered the following problem studying for my test, with no answer published to it: 1)Maximum double matching problem- given a bipartite graph G=(V=(LUR),E) describe an algorithm that returns ...
0answers
92 views

### Shortest path as a max flow problem

Using a road network, we were given the task to find the shortest path using various algorithms for each team, and our team was given the Edmonds–Karp algorithm to implement it. But reading the ...