Stack Exchange Network

Stack Exchange network consists of 174 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
6 views

Data structure for assignment problem with quick update

I am looking for a data structure, which can be used to solve the following problem, while allowing quick modifications. Consider a box as shown in the image below. In the red box we have a binary ...
0
votes
1answer
33 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
17 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
38 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 ...
0
votes
0answers
11 views

Fairly partitioning workload using network flows

I have the following question to answer: A fraternity has n student members. In Fall’18, m courses are being offered and for each course i, some subset $S_i$ of the fraternity members are taking the ...
0
votes
0answers
23 views

Help with understanding Kleitman–Wang algorithm

I have a problem in which I need to solve the realization for a directed graph when I am given the in and out degrees for n number of vertices. A hint was to use network flows. I know that the ...
0
votes
0answers
37 views

New IPv4 with fragmentation at source only

Apologies for the long post. I am working on a project and need some inputs. The project is to device a decentralized fragmentation algorithm/ protocol at the network layer. While in IPv4 - ...
1
vote
1answer
78 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 ...
0
votes
0answers
19 views

Modelling the following Entscheidungsproblem as the flow network problem

We have sensors that collect data and send them from time to time as packet to a center node in the network.We want to study if we can achieve that in T steps.So let´s consider a graph G=(V,E) a ...
1
vote
2answers
72 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
0answers
27 views

How to find all paths from a certain collection of nodes to another, without any common nodes in any of the paths?

For example i am given a undirected Graph G = (V, E). Within that graph i have a certain collection of nodes D and S. Now i need to find paths from D collection of nodes to S, without any two paths ...
0
votes
1answer
27 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
230 views

Maxflow problem

My thought was to make all edge weights have capacity $c$. Then, just use Ford-Fulkerson to find paths in the residual graph. But I'm not sure if this is the right approach because maybe we will have ...
0
votes
1answer
24 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 ...
0
votes
0answers
18 views

Can ideas of maximum flow be used to solve the problem of traffic?

So I'm considering the problem of traffic congestion. I was wondering if it is possible to solve the problem of Maximum Flow on a graph representing a city, at least in theory (lets say you have ...
1
vote
0answers
8 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
0answers
37 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
39 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
172 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
32 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
38 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
80 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
62 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
79 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
68 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
143 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
34 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
27 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
26 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
18 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 ...
1
vote
1answer
525 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 ...
0
votes
0answers
10 views

Size of flow in a flow network with a vertex in the middle

Suppose we have a flow network $G(E,V)$, for each 3 vertices $x,y,z$, prove/disprove: if the max flow from source $x$ to drain $z$ is at most $n$, then the flow from source $x$ to drain $y$ is at most ...
0
votes
0answers
123 views

Examples of “reverse edges” being useful in residual network in Ford-Fulkerson's method for maximum flow problem [duplicate]

I'm trying to understand why we need "reverse edges" in residual network in Ford-Fulkerson's method as described in Introduction to Algorithms (3rd edition). From the text, it "allow an algorithm to ...
2
votes
0answers
49 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
735 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.
0
votes
0answers
17 views

Creating a Visual Model of Network Traffic Flow

I am a beginner in computer science and networking softwares. I need some help creating a visual model of network traffic flow. I want to create a visual model of a network in flux and the end-to-end ...
0
votes
0answers
82 views

Polynomial time algorithm to decide whether it is possible to keep set of phones fully connected (Kleinberg 7.26)

This is a problem from Kleinberg & Tardos textbook. We are given the locations of n base stations, specified as points b1, . . . , bn in the plane. We are also given the locations of n cellular ...
0
votes
0answers
18 views

How to calculate the centrality index of a edge in multiple source sink max-flow min cut algorithm?

I trying to implement a paper on power system vulnerabilty analysis using ford fulkerson algorithm.Basically the whole central idea in this paper was to take the nodes as generators , bus bars and ...
0
votes
0answers
116 views

what is network forward/reverse star presentation is for?

i am learning about forward/reverse star presentation of networks . but i don't know why do we use them anyway ? can't find a direct wikipedia link , but some of examples could be found here network ...
2
votes
1answer
622 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
85 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
233 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
94 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
120 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 ...
0
votes
1answer
122 views

Flows with Negative Values?

Define a "non-standard" flow to be a flow where the quantity flowing through an edge may be negative. Formally, given a directed graph $G$, and two designated and distinct vertices $s$ and $t$ (...
2
votes
1answer
146 views

Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text

I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design". ...
2
votes
3answers
256 views

Max flow with priorities

I'm studying a simple max flow problem: Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph: There are $|a_i|$ objects of the type ...
3
votes
0answers
35 views

Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
2
votes
1answer
405 views

What is the time complexity of finding the residual network in this case?

Here are the details: (1) We are given a number $f$ of units of flow that we wish to transmit from the source node to the sink node. For example, $f=5$ units of flow (data or goods) should be ...
2
votes
1answer
222 views

Min-cut in DAGs with unit edge weights

I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut ...