Computing Minimal Spanning Subgraphs in Linear Time

Abstract:

Let $P$ be a property of undirected graphs. We consider the following
problem: given a graph $G$ that has property $P$, find a minimal
spanning subgraph of $G$ with property $P$. We describe two related
algorithms for this problem and prove their correctness under some
rather weak assumptions about $P$. We devise a general technique for
analyzing the worst-case behavior of these algorithms. By applying the
technique to 2-edge-connectivity and biconnectivity, we obtain a tight
lower bound of $OMEGA (m^+^n$ log $n$) on the worst-case sequential
running time of the above algorithms for these properties; this
resolves open questions posed earlier with regard to these properties.
We then give refinements of the basic algorithms that yield the first
linear-time algorithms for finding a minimal 2-edge-connected spanning
subgraph and a minimal biconnected spanning subgraph of a graph.