Questions tagged [graph-cut]
The graph-cut tag has no usage guidance.
8 questions
7
votes
1
answer
413
views
Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?
$\DeclareMathOperator\cl{cl}$The cyclic edge connectivity $\cl(G)$ is the size of a smallest cyclic edge cut, i.e., a smallest edge cut $F$ such that $G-F$ has two connected components, each of which ...
- 1,851
2
votes
0
answers
135
views
Minimum cost k-edge connected subgraph
The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...
- 21
1
vote
0
answers
137
views
Maximum cut variation
Given an undirected graph $G=(V,E)$, the max-cut problem asks for the partition $S_1,S_2\subset V$ , s.t., the number of edges going from $S_1$ to $S_2$ are maximized.
Is it possible to maximize the ...
0
votes
2
answers
255
views
Random Optimization on Graphs: Minimum Cut
Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
- 1,096
1
vote
0
answers
92
views
Karger's algorithm randomized min cut - probability of not contracting a particular edge
I know how Karger's algorithm works, and that the probability of finding a min-cut is over $1/n^2$. My question is the following. How can I find the probability of not contracting edges of a min-cut ...
- 11
2
votes
0
answers
228
views
expected number of edges for fixed min cut
It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.
Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
- 21
1
vote
1
answer
1k
views
Minimum spanning subgraph with at least one incoming and one outgoing edge
Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...
- 723
1
vote
1
answer
390
views
almost-bipartite nearly-isolated subgraphs
I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges ...
- 6,962