Sparse connectivity certificates via MA orderings in graphs

For an undirected multigraph G = (V, E), let alpha be a positive integer weight function on V. For a positive integer k, G is called (k, alpha)-connected if any two vertices u, v is an element of V remain connected after removal of any pair (Z, E') of a vertex subset Z subset of V - {u, v} and an edge subset E' subset of E such that Sigma(v is an element of Z)alpha(v) + vertical bar E'vertical bar < k. The (k, alpha)-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a (k, alpha)-connected graph G, we show that a (k, alpha)-connected spanning subgraph of G with O(k vertical bar V vertical bar) edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the (k, alpha)-connectivity. (c) 2006 Elsevier B.V. All rights reserved.