A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges
Given a network with n vertices and m edges where each edge has an independent operational probability, we are interested in finding a vertex of the network whose expected number of reachable vertices is maximum. Such a vertex is called a most reliable sourer of the network. This problem was studied by Melachrinoudis and Helander (1996) where an O(n(2)) time algorithm was proposed when the given network is a tree. In a more recent paper, Xue presented an O(n) time algorithm for this problem when the given network is a tree, in this paper, we present an O(n) time algorithm for computing the most reliable source on series-parallel graphs, using their embeddings in 2-trees. (C) 1998-Elsevier Science B.V. All rights reserved.
algorithms series-parallel graph time complexity partial 2-trees network reliability