THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES IN 2-TERMINAL SERIES-PARALLEL GRAPHS

Abstract

A set E' of k edges in a multigraph G = (V, E) is said to be a k most vital edge set (k-MVE set) if these edges being removed from G, the resultant graph G' = (V,E - E') has minimum number of spanning trees. The problem of finding a k-MVE set for two-terminal series-parallel graphs is considered in this paper. We present an O(Absolute value of E) time algorithm for the case k = 1, and an O(Absolute value of V(k) + Absolute value of E) time algorithm for arbitrary k.