✦ LIBER ✦

Linear time algorithms for computing the most reliable source on an unreliable tree network

✍ Scribed by Xue, Guoliang

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 121 KB
Volume: 30
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199708)30:1<37::aid-net5>3.0.co;2-m

No coin nor oath required. For personal study only.

✦ Synopsis

Given a tree network with n vertices where each edge has an operational probability, we are interested in finding a vertex on the tree whose expected number of reachable vertices is maximum. This problem was studied in Networks 27 (1996) 219-237, where an O(n 3 ) time algorithm and an O(n 2 ) time algorithm were proposed. In this paper, we present an O(n) time algorithm for the same problem, improving the previously best algorithm by a factor of O(n). We also study a max-min version of the problem and propose an O(n) time algorithm for this problem as well. Examples are provided to illustrate the algorithms.