标题: 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
显示于类别:Articles


文件中的档案:

  1. A1992JR59200003.pdf

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.