Title: | THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES IN 2-TERMINAL SERIES-PARALLEL GRAPHS |
Authors: | JAN, RH HSU, LH LEE, YY 資訊工程學系 Department of Computer Science |
Keywords: | MOST VITAL EDGES;SPANNING TREES;2-TERMINAL SERIES-PARALLEL GRAPHS |
Issue Date: | 1992 |
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. |
URI: | http://hdl.handle.net/11536/3587 http://dx.doi.org/10.1007/BF02074877 |
ISSN: | 0006-3835 |
DOI: | 10.1007/BF02074877 |
Journal: | BIT |
Volume: | 32 |
Issue: | 3 |
Begin Page: | 403 |
End Page: | 412 |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.