2006-12: Generating 3-Vertex Connected Spanning Subgraphs

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