Title: FINDING THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES
Authors: TSEN, FSP
SUNG, TY
LIN, MY
HSU, LH
MYRVOLD, W
應用數學系
資訊工程學系
Department of Applied Mathematics
Department of Computer Science
Keywords: RELIABILITY OPTIMIZATION;NUMBER OF SPANNING TREES;MOST VITAL EDGES;MATRIX OPERATION
Issue Date: 1-Dec-1994
Abstract: 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
Journal: IEEE TRANSACTIONS ON RELIABILITY
Volume: 43
Issue: 4
Begin Page: 600
End Page: 603
Appears in Collections:Articles


Files in This Item:

  1. A1994QC59900016.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.