The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
144 views

karger's algorithm contracting nodes not edges [closed]

Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge). Is there a reason why this is so?
5
votes
0answers
186 views

Weighted vertex-connectivity; global min vertex-cut

I am interested in the following problem: Input: a connected undirected graph $G=(V,E)$; a positive weight for each vertex. Output: a minimum weight subset of $V$ whose removal disconnects ...
5
votes
2answers
2k 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
90 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
137 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
274 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 ...
1
vote
0answers
101 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
205 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
228 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
140 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 ...
14
votes
3answers
770 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 ...
8
votes
1answer
711 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 ...
5
votes
2answers
1k 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
407 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 ...