A LINEAR-TIME ALGORITHM FOR FINDING A SPARSE K-CONNECTED SPANNING SUBGRAPH OF A K-CONNECTED GRAPH

We show that any k-connected graph G = (V, E) has a sparse k-connected spanning subgraph G' = (V, E') with \E'\ = O(k\V\) by presenting an O(\E\)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time bound O(max{k2\V\1/2, k\V\}\E\) to determine whether node-connectivity kappa(G) of a graph G = (V, E) is larger than a given integer k or not can be reduced to O(max{k3\V\3/2, k2\V\2}).