The max-flow tag has no wiki summary.
2
votes
1answer
87 views
Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices
Consider the standard minimum-cost flow problem presented here. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and ...
-1
votes
0answers
36 views
Bound on vertex heights in Push-Relabel
I'm having a little bit of trouble understanding Lemma 26.20 in CLRS 3rd Edition. It states that on a graph $G=(V,E)$, $\forall v \in V, h(v) \leq 2|V| - 1$. I can see the intuition behind the proof, ...
1
vote
0answers
30 views
Length functions in blocking flows
I've been attempting to read Goldberg & Rao's paper Beyond the flow decomposition barrier, and found that I could not understand the blocking flow component of the paper. I then found Karger's ...
2
votes
2answers
203 views
Fastest way to find an s-t min-cut from an s-t max-flow?
Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity.
How could I use a sparse s-t flow to find an s-t min-cut in time ...
1
vote
1answer
84 views
Max flow with conditional edges
Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?
Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.
7
votes
1answer
277 views
Goldberg&Tarjan: How to find a blocking flow in a graph
I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a blocking ...
3
votes
1answer
121 views
Can I get all min-cuts after executing Push-Relabel?
The push-relabel algorithm (here is push-relabel as pseudo-code) assigns a distance-label to each node.
After executing push relabel, you have those distance labels and a max flow in a given network ...
22
votes
2answers
649 views
Are any of the state of the art Maximum Flow algorithms practical?
For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an ...
-1
votes
1answer
141 views
The existing bound on Edmonds-Karp doesn't seem to be tight
I'm reading CLRS's (Cormen et.a al) Introduction to Algorithm, and arrived at the maximum flow section. It shows that Edmonds-Karp algorithm runs in $O(E^2V)$ time by showing that:
1) If we let ...
6
votes
1answer
158 views
multi-commodity flow acyclic digraphs
I am faced with the following question on max. integer multiflow:
INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function ...
1
vote
2answers
244 views
Viapath as a maximum flow problem
Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \ $ different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a ...
5
votes
1answer
458 views
Minimum path edge-cover or minimum flow with unit capacities and DAGs
I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths ...
0
votes
2answers
570 views
shortest path & max flow
I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book.
We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ ...
4
votes
0answers
143 views
Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two
It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
0
votes
0answers
481 views
A question about the Edmonds-Karp algorithm [closed]
My question is related to the maximum network flow problem.
We know that the "simple" implementation of the Ford-Fulkerson method, which uses BFS to find the augmenting path in the residual network ...
20
votes
1answer
813 views
Maximum flow using Ford-Fulkerson and DFS
This question is about the time complexity of the Ford-Fulkerson
maximum flow algorithm when using DFS to find augmenting paths.
There is a well-known example showing that using DFS one can need a
...
