Questions tagged [network-flow]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
1answer
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-...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
21 views

Alternative maximum flow within a directed graph

I am having trouble with the following alteration to a max flow problem. If I have a directed graph $G(V,A)$ with arc capacities $c_i$ and a source/sink. Suppose $f$ is the max flow within $G$, is $...
2
votes
0answers
18 views

Ford-Fulkerson for maximum cardinality matchings

If I have a bipartite graph $G(V_1 \cup V_2)$ and I wanted to find the maximum matching. Why is it that the ford-fulkerson algorithm will take at most $min{(|V_1|,|V_2|)}$ iterations? I know that in ...
1
vote
1answer
30 views

Maximal Matching in Bipartite Graph with Degrees Given

I'm quite stuck on how to go about showing the second part of the following question: Assume $G(V,E)$ is a bipartite graph with bipartition $V = P\cup Q$ and every vertex in $P$ has degree $a$, and ...
0
votes
1answer
12 views

Extension of Integrality Lemma for min-max flow

The integrality lemma states that if all of the values of the capacities are integers, there is maximum flow in the network which uses an integer value on each edge. One of the ways to prove this is ...
0
votes
0answers
23 views

Relation between Cut Sets and (Minimum, Maximum) Flow Problems

For a given connected graph (with capacities attached to the edges) how can I find the minimum and the maximum flow of the graph using cut sets, spanning trees etc. The point is, I am having hard time ...
0
votes
1answer
131 views

Remove minimum number of nodes to make graph disconnected

Find the minimum number of nodes that need to be removed to make graph disconnected( there exists no path from some node x to all other nodes). Number of nodes can be 105
3
votes
2answers
40 views

Shortest Path Problem Minimization

I am asked to formulate shortest path problem as a min-cost flow problem. The textbook I am using is Gentle Intro to Optimization where it states the max netflow model for graph G with s, t ...
0
votes
1answer
31 views

Optimizing a shortest path problem

I am asked to formulate shortest path problem as a min-cost flow problem and I am stuck on the following step: Min cost flow probelm can be formulated as https://en.wikipedia.org/wiki/Minimum-...
0
votes
0answers
67 views

Finding an acyclic flow in a flow network with edge demands

Given a flow network (all capacities, demands, and flows are non-negative integers) with edge set $E$, define an acyclic flow as any flow $f: E\rightarrow \mathbb{N}$ so that if $F = \{e \in E| f(e) &...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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.
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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., ...
0
votes
0answers
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)=...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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. ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
69 views

Graph Theory exercise- feasible flow,network flow

Let $G = (V,E)$ be a digraph, $c : E \rightarrow \mathbb{R}_{+}$, and $X,Y \subseteq V$ be two disjoint non-empty subsets of vertices in $G$. Suppose that we have two functions $\sigma : X \rightarrow ...
0
votes
0answers
126 views

Graph-theory exercise: network flow, maximum flow

So I've got this exercise to solve for a homework and I've got no idea, any help would be appreciated, thanks in advance. At the CS department there are $p$ students $(S=\{S_1,S_2,\dots,S_p\})$ who ...
0
votes
0answers
20 views

Modified Project Allocation Problem(Graphs - Max. Flow related)

I have been assigned to solve a modified problem of the classic Project Allocation. We have x Contestants(C1,C2,...,Cx) and y Judges(G={J1,J2,...,Jy}). Groups of n Judges have to evaluate the ...
0
votes
1answer
46 views

How to find min cut in this flow network?

I have created a flow network and wondering what the min cut is. Clearly its a max flow since the edges out of $s$ are fully saturated. The algorithm to find min cut is to draw the residual and then ...
0
votes
0answers
42 views

Network Flow problem(Increasing the capacity of an arc by constant)

I would appreciate if someone give me a clue how I approach to answer this network flow problem question: Let $D=(V,E)$, source $s$, sink $t$, and integral capacity function $c$. Suppose we increase ...
0
votes
0answers
11 views

Decreaseing the value of maximum flow by decreasing some of the arc capacities?

Ii would be nice if someone has some idea how to solve this problem: We are given a network(a digraph $D=(V,E)$, source $s$, sink $T$ and integral capacity $c$) as well as positive integer $R$, which ...
0
votes
0answers
62 views

Construct network for the worst case complexity of Dinic's algorithm

I think I understand the complexity for Dinic's algorithm. There are at most $|V|$ possible level graphs, and $|V|*|E|$ time for the blocking flow in each phase because the DFS path guarantees to ...
0
votes
0answers
29 views

total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
2
votes
2answers
63 views

Construct a Network with constrained Maximum Flow

Seven types of chemicals are to be shipped in five trucks. There are three containers storing each type of chemical, and the capacities of the five trucks are 6, 4, 5, 4, and 3 containers, ...
0
votes
0answers
21 views

Network flow and uncertainty in supply/demand

I am trying to learn how to study uncertainty in supply in a network flow problem. Specifically, I am using network simplex method on an undirected graph with a bunch of nodes with source/supply and a ...
0
votes
1answer
36 views

Show that there is a flow network with a bottleneck of 1 where the mac flow is greater than 1.

Using a Ford-Fulkerson algortihm with the restriction that it cannot decrease the flow on an edge, find a flow network with $f>1$ where this algorithm terminates after finding a flow of $ 1 $. It'...
2
votes
2answers
36 views

Weighted matching in sink source graph

I have three lists of nodes. sources, sinks, and pipes. there is a directed weighted graph from sources to pipes to sinks. Sources are only connected to pipes and pipes only to sinks. But sources are ...

1
2 3 4 5
7