## DIMACS TR: 2006-12

## Generating 3-Vertex Connected Spanning Subgraphs

### Authors: Endre Boros, Konrad Borys, Vladimir Gurvich and Gabor Rudolf

**
ABSTRACT
**

In this paper we present an algorithm to generate all
minimal $3$-vertex connected spanning subgraphs of an undirected
graph with $n$ vertices and $m$ edges in incremental polynomial
time, i.e., for every $K$ we can generate $K$ (or all) minimal
$3$-vertex connected spanning subgraphs of a given graph in $O(K^2
log (K) m^2 + K^2 m^3)$ time, where $n$ and $m$ are the number of
vertices and edges of the input graph, respectively. This is an
improvement over what was previously available and is the same as
the best known running time for generating $2$-vertex connected
spanning subgraphs. Our result is obtained by applying the
decomposition theory of $2$-vertex connected graphs to the graphs
obtained from minimal $3$-vertex connected graphs by removing a
single edge.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-12.pdf

DIMACS Home Page