# Questions tagged [network-flow]

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

303 questions
Filter by
Sorted by
Tagged with
15 views

### Maximum bottleneck-capacity variant of Ford-Fulkerson: worst-case example

I am looking for a worst-case example (or series of examples) for the maximum bottleneck-capacity variant of Ford-Fulkerson (i.e. the path with the highest bottleneck-capacity is chosen as an ...
27 views

### Max Flow/Minimum Cut - Flow after removing K edges.

Given : A flow network G whose edges have capacity of 1 G's maximum flow |F| A positive integer K Delete exactly K edges so that the flow of the network is minimized. My thoughts : If K is greater ...
36 views

### The Satisfactory Conveyor Problem: how to calculate required splitting and merging of conveyors to get specific outputs from a known input?

With the rise of factory games like Satisfactory and Factorio, many people have started wondering about problems like these. Factorio already has a very interesting analysis of conveyor dynamics on ...
23 views

### Minimum cut with minimal number of edges

Given a flow network G=(V,E) from s to with pisitive integer capacities. Decribe an efficient algorithm that checks whether there exists a minimum cut that contains 100 edges at most. My try: Compute ...
16 views

### Network Flows - Nurse Scheduling Problem

Exercise Nurse Scheduling Problem Hello everyone! I'm in trouble with this Network Flow problem, that I have to implement on LPSolve. I drew this problem's network as Minimun cost flow, and now I'm ...
30 views

### Trasitivity of maximum flow [closed]

$G=(V,E)$ is a directed graph, $C(e)>0$ for all edges. Is the following correct? For every $3$ vertices, $u,v,w$, if the max flow from $u$ to $w$ is more than $1000$ and the max flow from $w$ ...
22 views

### Maximum Flow of a network $G$

We are supposed to find the maximum flow through this network $G$. We have that $val(f) \leq c(C)$ for every cut in the network, where $c(C)$ is the capacity of the cut $C$. So I understand I am ...
25 views

### Find matrices given sums of each row and column with bounded integer entries: maximize zero-valued entries

I want to find solutions for the following problem. It seems to be a classic problem in integer programmimg and logistics, but I don't know its name. Find a matrix of m rows and n columns, with non-...
22 views

### Proof for Gossip problem

Suppose there are n people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information ...
10 views

### Is there a way to represent a Max Flow problem as a dynamic programming task?

I've recently started practising some graph theory problems, and I wanted to know if there is a method which would allow us to approach the Max Flow problem through dynamic programming. I cannot seem ...
13 views

### Size of the set T in a T-join problem

I am an undergraduate that is taking a course in combinatorial optimization and I have come onto studying T-join problem. Could someone please explain why the size of the set $|T|$ has to be even in a ...
21 views

40 views

### How can I calculate the minimum number of moves needed in a game involving stacks?

I'm currently programming a game, and I have been stuck on the following problem for a while. The above figure is a set of stacks. The end-goal is to sort all items by color in the least possible ...
87 views

### Going from abstract intuition to formal proof

This question is somewhat open-ended and there is unlikely to be a single fixed answer to this, but I would love to hear some thoughts of the people with a deeper understanding of this field than I ...
19 views

### show maximum number of arc disjoint directed $s-t$ paths is equal to max flow

Given: $D = (V,A)$ a directed graph and $s,t \in V$ Problem: Show that the maximum number of pairwise arc-disjoint directed $s-t$ paths is equal to the maximum value of the flow $f$ where $f$ is ...
19 views

### Can there be an edge with a positive capacity directly from the source to the destination in a network?

I was hoping to use this in a proof of mine. I do not see any problems with this being the case, however, I have never run into example graphs with this so I was curious.
33 views

### Help formulating an inventory problem

I need some advice on how to describe this as an optimization problem. There are a number of items stored in warehouses, that need to be reorganized in order to minimize new purchases. To illustrate ...
36 views

### Prove that if (S, V − S) is an arbitrary mincut of N, then c_f (x, y) = 0 for all x ∈ S and y ∈ V − S

Some backgroud- Let N = (G = (V, E), c, s, t) be a network, f be a maxflow in N, Nf = (Gf = (V, Ef ), cf , s, t) be the residual network of N with respect to f, S∗ be the set of vertices reachable ...
33 views

### construct graph using max flow algorithm

Given n pair of integer (di, dj), e.g. (0, 2), (1, 1), (1, 0), (1, 0)... Construct a directed graph G = ({1...n}, E) such that in-degree of vertex 1 is di and out-degree is dj. Is it possible to ...
27 views

### Ford Fulkerson MaxFlow dCut

Question is the following: Z={A,B} subset of V containing all Nodes. State dCut({Z}, G). Does the above dCut induce an upper bound to the maximum s – t flow value? If so,what is the induced upper ...
33 views

### Network Flow Optimization

Suppose we have a network with node set $N = \{1,\dots, n\}$ and arc set $E$. $(i, j) \in E$ if there is a link between node $i$ and node $j$. We need to send $L$ commodities from their respective ...
12 views

### Digraph: Flow with length constraint

I'm considering the following problem: Given a directed graph $G = (V,A)$ with unit capacities, determine if there exists a flow from $x$ to $y$ ($x = y$ is allowed) with a specific length $k$, i.e., ...
22 views

### Two disjoint minimum cuts in a flow network

I was studying flow networks and intersection/union of min cuts in such networks, Im trying to prove a theory that says if the intersection of two min cuts A, B had s in it (meaning (A)intersection(B)=...
7 views

### min-cut - max-flow: A flow that saturates every cut has a maximal flow?

I need some help understanding if this claim is correct: Given a flow network $N$ and a flow $f$ on this network. It is given that for every minimal cut $<S,T>$ , $f(e)=c(e)$ for every edge ...
43 views

### Algorithm for max flow and min cut, simultaneous

Good morning everyone. I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems was asking for an ...
35 views

### Values of $s-t$ flows and cuts

$G = (V, A)$ is a directed graph where all arcs in $A$ have a capacity of $1$. The shortest length path in $G$ from $s$ to $t$ consists of exactly $d$ arcs. G has a total of $m$ arcs and $n$ vertices. ...
37 views

### Uniqueness of a minimum capacity $s-t$ cut

Two vertices $x$ and $y$ form an arc that is part of a minimum capacity $s-t$ cut in a directed graph $G = (V, A)$. Prove that another minimum capacity $s-t$ cut cannot exist in $G$ if it only ...
33 views

### Max flow in simple weighted graph with no specified source or sink

I am modeling a traffic network with a simple edge-weighted graph. The edge weights represent the capacity of each road. I would like to measure the maximum flow the network can accept. In order to ...
108 views

### Does the maximum bottleneck-capacity variant of Ford-Fulkerson always terminate?

We know that the generic Ford-Fulkerson Algorithm may not terminate in the presence of irrational capacities and that its maximum bottleneck-capacity variant always terminates within weakly polynomial ...
20 views

### A special condition on the Minimum Cost Flow Problem

I am working on the following exercise: Consider the minimum cost flow problem with the following additional constraint: For each vertex $i \in V$ we are given an upper bound $w_i$ for the amount ...