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
0
votes
0answers
155 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
352 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 ...
1
vote
1answer
3k 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
367 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". ...
4
votes
3answers
801 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 ...
2
votes
0answers
40 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
2k 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
885 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 ...
5
votes
0answers
69 views

Network Reconstruction from Flow Function

Suppose that $T$ is a set of vertices in an unknown network. We have oracle $F(X,Y)$ that returns maximum flow value between $X, Y \subseteq T$ in the unknown network. Can we reconstruct the unknown ...
2
votes
1answer
2k views

Residual graph of a graph with bidirectional edges?

Let's suppose we have a directed graph $G$ which has at least a pair of vertices $v,w$ such that $(v,w) \in E, (w,v) \in E$. $e.g:$ In the example, there is an edge going from $C$ to $A$ and ...
1
vote
1answer
134 views

Optimal covering of 2D matrix elements given spatial constraints

I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction. I've ...
0
votes
1answer
117 views

How to balance the inflow and outflow of each vertex in a bipartite graph?

I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with ...
2
votes
1answer
164 views

Variant of bipartite matching, with real capacities from source and to sink, all others unlimited

I've got a variant of bipartite graph matching and I can't find any literature about it. We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real ...
1
vote
0answers
967 views

Simple Path between 2 nodes passing through specific nodes

I have an unweighted undirected graph and I have to find if there exists a path between two vertices $u,v$ that visits set of specific nodes $A$. $A$ can contain $1-10$ nodes. No node can be visited ...
0
votes
0answers
121 views

Edmonds-Karp Maximum Flow Algorithm

Referring to Tim Roughgarden's Lecture Note - 2 (page 11) on CS261 at Stanford following statement and the para seem quite confusing. Claim: d(f) never decreases during the execution of the Edmonds-...
0
votes
0answers
95 views

Push–Relabel Maximum Flow Algorithm $x_f(s)\leq0$

I'm looking at Push–Relabel Maximum Flow Algorithm (or Goldberg-Tarjan Algorithm) and trying to solve some homework question. As part of the answer I'm trying to prove $x_{f}(s)\leq0$ during the ...
0
votes
1answer
437 views

Maximum flow properties

I was trying to solve problems in max flow algorithms. And I came across this MIT Lecture Quiz. http://people.csail.mit.edu/moitra/docs/6854hw4.pdf solution : http://people.csail.mit.edu/moitra/docs/...
0
votes
0answers
75 views

Applying Ford-Fulkerson to settle a business lunch

I want to organize a business lunch with two societies $E_1$ (mine) and $E_2$. Each society is made of four people from the Executive management and 6 of the Financial Management. I want to organize ...
-2
votes
1answer
32 views

What's the complexity of running an algorithm that searches over all cuts on a network and returns the minimum?

It's a question of a problem set. If I search for all possible cuts on a network graph and return the minimum, (so it will be equal to max flow), what will be the complexity of running this?
4
votes
1answer
311 views

New Applications of Network Flow

I am thinking of explaining the topic of Network flow to an audience of computer sciecne students, and I want to make it more enjoyable by giving some real life examples where a software Developer may ...
2
votes
1answer
1k views

Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes

TL;DR: There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture: E.g., look at ...
3
votes
2answers
558 views

In a flow network, is it possible to restrict the flow going into a node?

For example, if a node has 2 edges going into it and two edges coming out of it all with capacity 1, is there a way to make it so that only 1 unit of flow can go through this node (without just ...
0
votes
0answers
1k views

Is there a procedural way to find minimum s-t cut without guessing cuts?

I was reading about max flow theorem and there I saw scenario where the min s-t cut is found. But wherever I searched they did it after knowing the max flow or by guessing the cuts by iterating ...
1
vote
0answers
61 views

An impartial game of snake

There is a display of NxN (N<=90) pixels with some blocked pixels and a snake of width = 1 pixel and variable length and two players A and B play a game. The game proceeds as follows - Both ...
2
votes
1answer
102 views

Improvement of algorithm due to constrained graph

This algorithm runs natively in O(V * E^2). The description states that The running time of O(V * E^2) is found by showing that each augmenting path can be found in O(E) time, that every time at ...
0
votes
0answers
228 views

How to uniquely determine a min-cut? [duplicate]

There are possibly several min-cuts for the source and target nodes of a graph. I think I can determine the same min-cut for the same graph by putting the following restriction "if there are ...
1
vote
0answers
103 views

Paris-Traceroute and Traceroute Difference

I am trying to understand the difference between Paris-traceroute and normal traceroute. I am using this website ( https://paris-traceroute.net/about) and trying to get the idea, what is Paris-...
3
votes
1answer
4k views

Checking if a given flow is a maximum flow

I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow $f_e$ is the maximum flow of the flow graph $G$ in $O(|E|)$ time complexity. ...
1
vote
0answers
116 views

End-to-end bandwidth allocation to n pairs of nodes

Suppose there is a weighted graph representing a network with available bandwidth. I want to allocate end-to-end bandwidth between a set of pairs of nodes to transfer data. I want to find a path and ...
2
votes
1answer
222 views

Max flow not min cut?

I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking ...
0
votes
1answer
963 views

Sliding Window Protocol, waiting Time calculation

With regard to this explanation in finding Round Trip Time I tried attempting the following question Question Frames of $1000$ bits are sent over a $10^6$bps duplex link between two hosts. The ...
0
votes
0answers
15 views

Relationship between flow and resource consumption in VNFs (Middleboxes)

A middlebox consumes some resources (CPU ticks, RAM, etc.) to process a traffic, e.g., a IDS consume 50% CPU and 20% RAM to process a 100M bps flow. Here is the problem. 100M bps flow may consume ...
2
votes
1answer
216 views

Do not understand a lemma regarding dinics algorithm

Here you can find the following lemma with its proof. Lemma: In a network with unit edge capacities, Dinitz algorithm terminates after $O(\sqrt{m})$ blocking flow computations. Proof: Consider the ...
1
vote
1answer
196 views

Is there an example of Dinitz's algorithm running with the worst time complexity?

I am trying to find a network, where Dinic's algorithm makes $|V|^2*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite ...
1
vote
1answer
267 views

Operation of the Ford–Fulkerson algorithm given an almost maximum flow [closed]

I have been assigned the question: Let $G$ be a flow network and $f^*$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $G'$ constructed by increasing the ...
4
votes
1answer
155 views

Allocating flows in a network while avoiding a particular node

I am considering a network with the max flow problem in a particular situation. I have a set of flows which should pass a certain node A and and another set of flows which should avoid A and pass ...
-1
votes
1answer
1k views

Network Flow - Bipartite Matching: Doctors Without Weekends Problem

Problem You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next n ...
1
vote
0answers
193 views

What is the worst case scenario for Dinitz's algorithm?

The complexity of Dinitz's algorithm (used to find maximum flow in a network) is O(V²E). I am trying to find a network, which is forcing the algorithm to use as much steps as possible. I was thinking ...
4
votes
1answer
4k views

Algorithm for solving incremental max flow problem

I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed ...
5
votes
1answer
510 views

Min-cut in graph with demands/lower bounds

This week I read something about network flow from Algorithm Design. But I am confused about some concepts. We say, if a graph G contains some nodes with demands, positive or negative, how to define ...
1
vote
1answer
3k views

Unique min-cut means unique max flow?

This is not a home work question. Is that correct to say in a flow network, if min cut is unique then max flow must also be unique? Assume we have two max flow in a network. Then for each max flow,...
2
votes
0answers
516 views

Bhandari Algorithm: Canceling Edges

I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
9
votes
2answers
2k views

Reducing max flow to bipartite matching?

There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item ...
2
votes
1answer
2k views

What actually is Blocking flow problem?

I am facing a hard time understanding Blocking Flow problem. This is what I have understood till now : We have a graph and in blocking flow problem we find all shortest paths from source to ...
1
vote
0answers
1k views

Minimum Cost Max Flow with Negative Weight Cycles?

Does there exist an algorithm that can solve the minimum cost maximum flow problem even if the residual graph contains negative weight cycles? I have an implementation that uses shortest paths to ...
2
votes
0answers
348 views

Minimal Separator / Vertex disjoint Paths

I'm in need of implementing the algorithm to actually locate the minimal vertex separators set of the whole graph (not just s-t). It is my understanding that this can be done by doing the s-t ...
1
vote
1answer
298 views

Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?

I'm working with a flow network like the following: The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, ...
0
votes
0answers
292 views

What's the relationship of max-flow-min-cut and Markov Random Fields?

I am trying to follow this paper [1]. There is a relationship between Markov Random Fields (MRF) to max-flow-min-cut. An MRF can be represented as an undirected graph, and you can find flow through it,...

1 2 3
4
5
7