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.

309 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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$ (...
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". ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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/...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...