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

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

0.00 Avg rating0 Votes
Article ID: iaor20021953
Country: United States
Volume: 30
Issue: 1
Start Page Number: 37
End Page Number: 45
Publication Date: Aug 1997
Journal: Networks
Authors:
Abstract:

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(n3) time algorithm and an O(n2) 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.

Reviews

Required fields are marked *. Your email address will not be published.