標題: THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES IN 2-TERMINAL SERIES-PARALLEL GRAPHS
作者: JAN, RH
HSU, LH
LEE, YY
資訊工程學系
Department of Computer Science
關鍵字: MOST VITAL EDGES;SPANNING TREES;2-TERMINAL SERIES-PARALLEL GRAPHS
公開日期: 1992
摘要: 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
期刊: BIT
Volume: 32
Issue: 3
起始頁: 403
結束頁: 412
顯示於類別:期刊論文


文件中的檔案:

  1. A1992JR59200003.pdf