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.
$\begingroup$
$\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 NikolovCommented Oct 19, 2011 at 16:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
For edge connectivity rather than vertex connectivity, there's always the Gomory–Hu tree.
answered Oct 17, 2011 at 15:00
$\begingroup$
$\endgroup$
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/
