7
$\begingroup$

I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k>3$, or perhaps approximate minimum cuts produced by Karger's algorithm. SPQR trees answer this question for 2-connected graphs. And obviously 1-connected graphs are simply a tree of their 2-connected components.

$\endgroup$
1
  • $\begingroup$ just a note: Karger's algorithm is not usually thought of as an approximation, but as a Monte Carlo algorithm. It produces the exact min cut with high probability. $\endgroup$ – Sasho Nikolov Oct 19 '11 at 16:16
5
$\begingroup$

For edge connectivity rather than vertex connectivity, there's always the Gomory–Hu tree.

$\endgroup$
0
4
$\begingroup$

Nagamochi and Ibaraki gave an algorithm to find a sparse $k$-node-connected subgraph of a given graph $G$ that contains $O(k n)$ edges where $n$ is the number of nodes in $G$. Not directly relevant perhaps but could be a useful preprocessing step. http://www.springerlink.com/content/u334lr0418n1719u/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.