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
1
vote
2answers
365 views

Why do source and sink have to be distinct in Ford-Fulkerson?

Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard,...
1
vote
0answers
982 views

All minimum cuts in flow network

I'm trying to prove that for a flow network, maximum flow f, and each minimum cut S that ...
1
vote
1answer
768 views

How do bridges divide a larger network into smaller broadcast domains?

I am recently brushing up my computer network knowledge, and came across a seemingly peculiar statement: A network bridge divides a network into smaller broadcast domains. As far as I could grasp ...
0
votes
0answers
1k views

Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
0
votes
1answer
44 views

It is necessary to minimize the functional

Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height ...
4
votes
0answers
64 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
5
votes
1answer
212 views

Set of vertex-disjoint cycles maximizing different colored vertices

Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$. I am looking to find a set of vertex-disjoint cycles that: First maximizes the ...
2
votes
2answers
953 views

Basic questions about network flow calculations

Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to ...
2
votes
0answers
135 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
3
votes
1answer
610 views

Ford-Fulkerson algorithm with asymmetric adjacency matrix

Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \{1, 2, \dots, n\}$, $B = \{1, 2, \dots, m\}$. After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want ...
1
vote
0answers
302 views

Maximum number of paths which do not use the same edge at the same time

Given a directed graph, consider the problem of finding the largest number of edge-disjoint paths from a source node $s$ to a destination node $t$. I know this can be done in polynomial time, for ...
12
votes
2answers
517 views

Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
0
votes
1answer
877 views

Maximum flow with Edmonds–Karp algorithm

I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.) If we first follow path S - A - C - T , we will get max ...
1
vote
1answer
256 views

Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
0
votes
1answer
352 views

Push relabel why return back to source

In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned: To make the ...
1
vote
2answers
141 views

PRAM with no bit operations and P vs NC

I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition anywhere....
0
votes
1answer
1k views

Multiple matching in Maximum Flow problem?

I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such: Assume there are x restaurants, each with a capacity q, and y people, each of ...
0
votes
0answers
919 views

Max Flow / Linear Programming Reduction Variant

While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause: Here are two variants of the standard Maximum Flow problem. Show that both of them can be ...
20
votes
2answers
45k views

Residual Graph in Maximum Flow

I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow? Can anyone help me ...
2
votes
0answers
273 views

Complexity class of maximum flow problem with random arc capacity

Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then ...
2
votes
0answers
184 views

Cheeger constant of a graph versus conductance of a Markov chain

Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some doubly-...
3
votes
1answer
1k views

Ford-Fulkerson Algorithm not "pushing back" flow

I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of ...
0
votes
0answers
437 views

Ford–Fulkerson algorithm. Counterexamples

Consider Ford–Fulkerson algorithm (FF). Look to wiki : The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source A and sink D. This example shows the ...
5
votes
1answer
2k views

Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

I stumbled across this question and answer (source): Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine ...
0
votes
1answer
39 views

How the website owner keep track of your times of access? [closed]

To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP ...
1
vote
0answers
74 views

Inequalities in a multicommodity min-cut max-flow theorem

I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow. In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil \ell(vw)...
1
vote
1answer
436 views

Reduce Min-Cut to 0/1 Integer Program

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by: $$ w(U,U^C) := \sum_{\{i,...
4
votes
2answers
2k views

maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the ...
2
votes
0answers
666 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
4
votes
0answers
147 views

Successive Shortest Paths vs Ford–Fulkerson

Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
1
vote
1answer
739 views

Does a path exist going through each color only once?

I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once. I think this problem can ...
0
votes
1answer
2k views

What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am ...
1
vote
1answer
785 views

Why is it that the flow value can increased along an augmenting path $p$ in a residual network?

I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement: the flow value can increased along an augmenting path $p$ in a residual network ...
-2
votes
1answer
399 views

Maximum flow, where such paths as source$\to$node$\to$sink must be ignored

How can the maximum flow of a graph be computed when all nodes of the graph are connected to both sink and source nodes (two hypothetical nodes), and the maximum flow method should ignore such paths ...
2
votes
1answer
268 views

A variation of the baseball elimination problem

I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still ...
1
vote
1answer
173 views

Why not use the channel capacity as the sliding window size?

In a sliding window protocol, if we use the maximum possible capacity of the channel as the size of the sliding window, efficiency will be theoretically 100%. What is the logic behind not doing this? ...
1
vote
1answer
62 views

What does this mean $[X]_1^T$?

I found this in information theory paper, P.3883* the authors states the following Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the fact ...
0
votes
0answers
381 views

Possible paths in pipe network, without loops and with some one-way valves

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit I have to ...
1
vote
1answer
52 views

Flow in a network: Conservation of flow definition

This might be too easy... But I just don't get it. I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network $\sum\limits_{...
19
votes
1answer
1k views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
-1
votes
1answer
5k views

Prove that Ford-Fulkerson can decide if there is more than one min cuts

Probelm: Deciding whether a network flow graph has more than one min cut. Optimal running time: O(V^2*E). I trying to prove the correctness of the next algorithm: run Dinitz to find max-flow and ...
3
votes
5answers
1k views

Why is this flow a max flow?

According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how ...
6
votes
2answers
3k views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...

1
3 4
5
6 7