The max-flow-min-cut tag has no wiki summary.
-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, ...
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
0answers
60 views
Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?
If we want a specific example, then how about the Erdos-Renyi random graph?
6
votes
0answers
75 views
Increasing the capacity to maximize the min cut
Consider a graph with all edges having unit capacity.
One can find the min cut in polynomial time.
Suppose I am allowed to increase the capacity of any $k$ edges to infinity
(equivalent to merging ...
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 ...
0
votes
0answers
74 views
Edge Cut of interval graphs
On interval graphs, minimal vertex separators are well understood: they are cliques, there are no more than $n$ ones. However, when we turn to the minimal edge cut, my search found no even one single ...
8
votes
1answer
192 views
Request for references on multicommodity flow-cut results
This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...
3
votes
0answers
188 views
Graph connectivity related game [closed]
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
3
votes
1answer
133 views
Primal Dual model in the continuous domain
The continuous max flow problem is posed as follows :
sup $\int_\Omega p_s(x)dx$
subject to :
$|p(x)| \le C(x); \forall x \in \Omega $
$p_s(x) \le C_s(x); \forall x \in \Omega $
$p_t(x) \le ...
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 ...
14
votes
3answers
742 views
Super Mario Flows in NP?
One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two ...
7
votes
1answer
517 views
Number of mincuts of a graph without using Karger's algorithm
We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.
I was wondering if we could ...
4
votes
2answers
752 views
Minimum cut through vertices/nodes - not edges
we all know and love s-t minimum cut algorithms, but they all cut through the edges in the graph. Are there any variants that cuts through nodes?
6
votes
3answers
382 views
In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial ...
