The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

Filter by
Sorted by
Tagged with
2
votes
0answers
26 views

Transit scheduling using flow networks

I am studying the maximum/minimum flow question, and was given the following problem: A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
3
votes
1answer
47 views

is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.
1
vote
1answer
27 views

Will a node with no incoming arc or no out coming arc affect the maximum flow?

So in a maximum flow question, say if we have a node which is not $s$ nor $t$, if it has no incoming arc, can we delete it without affecting the maximum flow? What if it has no output arc? How so?
0
votes
0answers
39 views

Minimum-cut with Maximal number of edges

My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts,...
2
votes
1answer
94 views

Minimum-cut with minimum number of edges

I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph. Firstly, let'...
0
votes
1answer
25 views

Efficient algorithm for assigning weights to nodes in graph to create steady state flow

I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem: Definitions: Given a graph $(V,E)$, with non-negative weights ...
0
votes
1answer
28 views

Maximum flow with maximum flow on specific edge

I am trying to solve the following problem: We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,...
0
votes
0answers
7 views

What is the average time for a node to transmit on the shared medium for Ethernet? (IEEE 802.3)

Suppose a shared ethernet link L, in which for nodes T1-T4 and a router R are connected: ...
1
vote
1answer
29 views

Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
1
vote
1answer
43 views

Minimum cost max flow network problem with an alternative flow cost

Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow ...
3
votes
1answer
46 views

Min cut of at most k edges

I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle. Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow ...
0
votes
0answers
17 views

Check valid flow in a graph

For a flow network $G=(V,E)$ where $s,t \in V$ and capacities $c_e>0$ for $e \in E$. A flow $f$ is given. How can I check whether of not $f$ is a valid flow within the network?
0
votes
0answers
24 views

Max flow through a specific edge

What i'v tried doing so far is to find a simple path from s to t containing e as well as some "bottle-neck edge" of maximal value (i.e. a simple path from s to t, containing e, whose minimum ...
0
votes
0answers
29 views

Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
0
votes
0answers
39 views

Proof of lemma from Hong's article about multi-threaded max flow algorithm

I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem. Lemma 3. Any trace ...
3
votes
1answer
63 views

Forcing an edge to be in S-T min-cut

Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e. So, I tried couple of steps, first, ...
2
votes
1answer
39 views

Maximum Flow in a Network

Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$. Prove or disprove: The value of a maximum flow for $N$ can’t be $56$. I'm trying to figure out how to ...
2
votes
1answer
26 views

Current value of flow in a network

Confused about a question regarding flow networks. Question is: Given the network below, what is the current value of flow in this network? Does the current flow of a network refer to the maximum ...
0
votes
0answers
42 views

What is the most efficient way to solve a workshop scheduling problem?

I am trying to design an algorithm to solve a workshop scheduling problem. The problem is as follows: I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
1
vote
0answers
27 views

Binary flow in max flow problem

is there a way ensure that there only is flow through vertices c and d and not e or through d and e and not c. But not both at the same time. With an simple extension it is possible to put also ...
4
votes
2answers
64 views

Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ...
0
votes
1answer
315 views

Ford-Fulkerson vs Edmonds-Karp

I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead ...
0
votes
0answers
20 views

Maxflow of graph equal to value of flow plus maxflow of residual graph

I'm reviewing max flow min cut for an upcoming exam and one of the proofs relies on the fact that for any flow $f$ on graph $G$ and residual graph $G_f$, $$\mathrm{maxflow}(G) = \mathrm{val}(f) + \...
0
votes
0answers
50 views

Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths

The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below. The notation ...
0
votes
0answers
17 views

Polynomial algorithm for determining if min-cut of network is unique?

How can I come up with an algorithm, that's polynomial, to determine if a given min-cut of some network is a unique min-cut or not?
0
votes
0answers
9 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 ...
12
votes
0answers
230 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
24 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
421 views

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

I am learning algorithms to solve Maximum Flow problem by reading the CLRS book and confused by the following figure: That is: A flow in a residual network provides a roadmap for adding flow to ...
2
votes
0answers
46 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
16 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
15 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
78 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 ...
2
votes
1answer
29 views

optimal flow for index multiple source and destination in directed graph

I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, ...
1
vote
1answer
317 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
16 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
40 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
32 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
147 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
85 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
23 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
169 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
17 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
98 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
571 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
231 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
528 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
212 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
33 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 ...