Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [network-flow]

Network flows are used to model concepts like traffic or water pipe systems. The basic idea is to move as many units of flow from source to sink nodes via edges with limited capacity.

0
votes
0answers
5 views

minimal broadcasting frame length in a CSMA/CD protocol

i'm unsure about the following question, would appreciate your assistance with it: in a CSMA/CD network with a cable length of L, and propagation speed T, with no need of repeaters(the signal is not ...
3
votes
0answers
30 views

Flow graph that requires pushing back flow in Ford Fulkerson

Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson? Let's assume we use the standard procedure of ...
0
votes
0answers
23 views

Affects of altering a line in “stop and wait” protocol(no noises)

what will happen if we change "to_physical_layer(&s)" to "to_physical_layer(&r)" in the following code(marked in the code where)? does it make the protocol fail? if so, show a scenario it ...
1
vote
2answers
385 views

Why CLRS example on residual networks does not follows its formula?

I am learning algorithms to solve Maximum Flow problem by reading the CRLS book and confused by the following figure: That is: A flow in a residual network provides a roadmap for adding flow to ...
-1
votes
0answers
35 views

divide a gold bar into minimum number of pieces so that it can be divided equally among 7,8 or 9 people

One night nine gangsters stole a gold bar. When the time came for dividing the bar, they faced a problem: two of the criminals put guns to each other's faces. Now it's up to fate whether one of them ...
2
votes
0answers
40 views

Find optimal redistribution in flow graph

I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of ...
0
votes
0answers
15 views

Finding current levels when encoding information in a channel

I am stuck with the following question: In a noised channel with a bandwidth of 4 kHz that has the signal-noise ratio of 30 decibels, if it is known that the maximal broadcasting speed is 16000 bps,...
0
votes
0answers
14 views

Maximal number of parallel cellular calls with no adjacent cells in a hexagonal setting

Is it possible to find an optimization to the following theoretical case? Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are ...
1
vote
1answer
32 views

Min-cut in a network with zero flow from source to sink

The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node ...
1
vote
1answer
94 views

residual graph and augmenting path in max flow

I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and ...
0
votes
1answer
14 views

What does flow denotes in the minimum-cost network?

What is flow in context of minimum-cost network? I know that a minimum cost network is a directed graph G={V,E}, where each edge has a cost and capacity value. The problem is to find best 'path' to ...
1
vote
1answer
35 views

What is a flow through the cut in the Ford-Fulkerson algorithm?

In page 12 of the slide, it states flow across a cut $(S, T)$ is $f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)$. I think the first part $\sum_{u\in S} \sum_{v\in ...
1
vote
1answer
31 views

Why c_f (u, v) = f (v, u) if f (v, u) not in E?

From page8 of the slide, I think $E$ is all the edges in the graph $G$. But why is $c_f (u, v) = f (v, u)$ if $f (v, u)$ is not in $E$? Why do we care about edge that is not in $E$?
0
votes
0answers
65 views

Successive shortest path without reduced costs

The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows : Successive shortest path (for minimum-cost flow) : while all flow is not ...
0
votes
1answer
29 views

Maximum flow with constraints

In a flow network, suppose we add constraints of the following type: The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$. Is maximum-flow with such constraints still ...
0
votes
1answer
19 views

transformation between two formulations of the mincost flow problem

According to this slide, the following two formulations of the mincost flow problem are equivalent: Given directed graph G = (V, E) Let u denote capacities Let c denote edge costs. A flow ...
1
vote
1answer
48 views

Why in Flow network ,there is no reversed edges?

I have read that Flow network is a directed graph , with no self loops and there is no reverse edges and non negative capacity. However in Residual network ,we allow the reverse edges so we can cancel(...
0
votes
0answers
14 views

Possible Network Flow “Cuts”?

The possibilities are: always full and always crossing. (True, per chart) always full and sometimes crossing. (True, per chart) always full and never crossing. (False?) sometimes full and always ...
1
vote
1answer
25 views

A repository for max flow and mincut datasets

I am not 100% sure if this is the right stackexchange to ask. I have a max-flow algorithm and I am also computing the min-cut from that algorithm. I want to test the correctness and speed of it and ...
-2
votes
1answer
297 views

Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification

I provided my answers in the "answer your own question" bit. I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though? a)...
0
votes
1answer
20 views

Do these answers work even when we change the values?

So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value? A) Suppose f is a flow of value 50 from s to t in a flow network G. ...
3
votes
1answer
116 views

How to calculate the minimum number of groups, by grouping groups with capacity together?

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem. If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
1
vote
1answer
295 views

Given max-flow determine if edge is in a min-cut

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
1
vote
2answers
106 views

How to prove that adding incoming edges to source node doesn't alter the max flow

I am given a homework assignment on this question: Show that if we add any number of incoming arcs, with any capacities, to the source node, the maximum flow value remains unchanged. Similarly, ...
0
votes
1answer
29 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
0
votes
1answer
349 views

Maxflow problem

I need help with the following practice problem on network flow: A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the ...
0
votes
1answer
187 views

The min number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ ...
1
vote
0answers
11 views

graph trend filtering results from different maxflow algorithm

We have followed the official code of the Graph trend filtering (GTF) https://arxiv.org/abs/1410.7690, and modified the code with Ford Fulkerson Algorithm (FFA) instead of parametric maxflow. The ...
1
vote
1answer
64 views

Possible ways to have cross and full edges in a mincut maxflow

I am trying to solve the following problem about maxflow mincut it seems like my conclusion is incorrect and I am wonder where. There is no graph just following question. An edge e can be (x) ...
1
vote
0answers
41 views

For a minimum cut $(S, T)$, why do edges entering $S$ have a flow value of $0$?

I'm studying for an exam and I'm having trouble with a specific question: Let there be a flow network $G = (V, E)$ with a maximum flow $f$ and capacity $c$, a source $s \in V$ and a sink $t \in V$, ...
5
votes
2answers
191 views

Minimum cost circulation problem with bounded number of edges

During an article I am writing, I encountered the following problem: Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$. ...
3
votes
0answers
35 views

Optimal flow in a network with non-constant edges' weights

I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
1
vote
1answer
117 views

Equivalence of minimum cost circulation problem and minimum cost max flow problem

In the following MIT open course, it is claimed that min-cost circulation reduces to min-cost max-flow: ... The second part of the proof is showing that min-cost circulation reduces to min-...
2
votes
1answer
235 views

Does minimum cost flow problem work for real valued edge weights/costs?

I'm a bit confused about the definition of the Minimum Cost Flow problem, in terms of the edge cost (or weight) values. I don't remember a integral requirement on the cost/weight values for the ...
1
vote
0answers
66 views

Minimum changes to be made to get Max-flow between each pair of vertices in an undirected graph

I was asked the following problem in an interview: Let M be a N X N matrix, such that: ...
3
votes
1answer
85 views

Students in classroom problem - Flow in network

I have room, which is opened some days in week, in different hours each day. I have multiple students, each has time some days in week, in different hours. Each student have to visit the room ...
3
votes
0answers
81 views

Introduction to the Traffic Light Scheduling Problem

I would like to understand the basics of how traffic light scheduling works. Looking through research papers the topics typically revolve around actual highway systems in urban areas, but also ...
2
votes
1answer
207 views

Self loops in max flow problem

So, there can be different types of edges in a directed graph while solving the max flow problem. There can be reverse edges, multiple edges and self loops. What is the significance of self loops in ...
1
vote
1answer
40 views

Minimum capacity cut reduction from digraph with two edge weight sets

Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{...
0
votes
0answers
30 views

MaxFlow Problem MinCut

Yesterday I found a question here, that asked, if the value of the flow across the edges of the MinCut is at capacity. I think the question has been deleted. But I want to confirm that for the edges ...
1
vote
1answer
36 views

Maximum flow in a graph, and conservation of flow

The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum_{v\in V}f(u,v)=0$ for every $u\not\in \{s,t\}$ where $s,t$ are the source ...
0
votes
1answer
20 views

Multi-type max-flow

Suppose you have $m $ sources $s_i$ and $n $ sinks $t_j$, but every source produces a certain type of flow, out of $k $ types, and every sink demands a certain type as well. We would like to know if ...
2
votes
1answer
740 views

Perfect matching in a bipartite regular graph in linear time

Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time. It is easy to show that there is a perfect matching for the graph, by using flow and ...
2
votes
0answers
66 views

long-lived scheduling using max-flow & push/relabel

I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
1
vote
1answer
1k views

What is a reducible flow graph?

What is a reducible flow graph? sorry if this is a stupid question but I'm having trouble finding an answer. Also multiple equivalent definitions and some motivation would be nice too.
2
votes
1answer
1k views

How to find max flow in a graph after decrementing an edge capacity?

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for ...
6
votes
0answers
95 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
1
vote
1answer
349 views

Minimal set of rows and columns covering all non-zero entries in matrix

Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns ...
0
votes
0answers
104 views

Will the Ford-Fulkerson method return any value if the residual network is ignored?

The normal Ford-Fulkerson method finds augmenting paths (as long as one exists) while including "back-flows", but if those back-flows are ignored, does there exist a flow network for which algorithm ...
0
votes
0answers
149 views

Running Time of Ford Fulkerson where all edges have equal capacity

My intuition says it would simply be the number of edges leaving s. I'm assuming it's a valid flow network so sum of capacities leaving s is the same as the sum of capacities entering t, so a max flow ...