<p>For edge connectivity rather than vertex connectivity, there's always the <a href="http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree">Gomory–Hu tree</a>.</p>

CC BY-SA 3.0
2011-10-17T15:00:07.913Z
2011-10-17T15:00:07.913Z
David Eppstein
<p>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.
<a href="http://www.springerlink.com/content/u334lr0418n1719u/" rel="nofollow">http://www.springerlink.com/content/u334lr0418n1719u/</a></p>

CC BY-SA 3.0
2011-10-17T21:43:17.990Z
2011-10-17T21:43:17.990Z
Chandra Chekuri
<p>I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k&gt;3$, or perhaps approximate minimum cuts produced by <a href="http://en.wikipedia.org/wiki/Karger%27s_algorithm" rel="noreferrer">Karger's algorithm</a>.  <a href="http://en.wikipedia.org/wiki/Triconnected_component" rel="noreferrer">SPQR trees</a> answer this question for 2-connected graphs.  And obviously 1-connected graphs are simply a tree of their 2-connected components.</p>

CC BY-SA 3.0
2011-10-19T16:16:00.653Z
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.
Sasho Nikolov
<graph-theory><co.combinatorics><graph-algorithms>
Are there nice generalizations of SPQR trees to k-connected components for k>3?
Jeff Burdges
# Are there nice generalizations of SPQR trees to k-connected components for k>3?

(Asked by: username_0 on 2011-10-16)

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](http://en.wikipedia.org/wiki/Karger%27s_algorithm). [SPQR trees](http://en.wikipedia.org/wiki/Triconnected_component) answer this question for 2-connected graphs. And obviously 1-connected graphs are simply a tree of their 2-connected components.

**Tags:** graph-theory, co.combinatorics, graph-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-10-17. Score: 5 | Accepted answer

For edge connectivity rather than vertex connectivity, there's always the [Gomory–Hu tree](http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree).


---

### Answer by username_3 on 2011-10-17. Score: 4

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/>


---

