標題: FINDING THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES
作者: TSEN, FSP
SUNG, TY
LIN, MY
HSU, LH
MYRVOLD, W
應用數學系
資訊工程學系
Department of Applied Mathematics
Department of Computer Science
關鍵字: RELIABILITY OPTIMIZATION;NUMBER OF SPANNING TREES;MOST VITAL EDGES;MATRIX OPERATION
公開日期: 1-十二月-1994
摘要: A most vital edge of a graph (w.r.t. the spanning trees) is an edge whose deletion most drastically decreases the number of spanning trees. We present an algorithm for determining the most vital edges based on Kirchoff's matrix-tree theorem whose asymptotic time-complexity can be reduced to that of the fastest matrix multiplication routine, currently 0(n(2.376)). The foundation for this approach is a more general algorithm for directed graphs for counting the rooted spanning arborescences containing each of the arcs of a digraph. A network can be modeled as a probabilistic graph. Under one such model proposed by Kel'mans, the all-terminal network reliability, maximizing the number of spanning trees is critical to maximizing reliability when edges are very unreliable. For this model, the most vital edges characterize the locations where an improvement of the reliability of the link most improves the reliability of the network.
URI: http://dx.doi.org/10.1109/24.370220
http://hdl.handle.net/11536/2189
ISSN: 0018-9529
DOI: 10.1109/24.370220
期刊: IEEE TRANSACTIONS ON RELIABILITY
Volume: 43
Issue: 4
起始頁: 600
結束頁: 603
顯示於類別:期刊論文


文件中的檔案:

  1. A1994QC59900016.pdf