✦ LIBER ✦

A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges

✍ Scribed by Charles J. Colbourn; Guoliang Xue

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 993 KB
Volume: 209
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00124-2

No coin nor oath required. For personal study only.

✦ Synopsis

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 source of the network. This problem was studied by Melachrinoudis and Helander ( 1996) where an O(n*) 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.

📜 SIMILAR VOLUMES

Linear time algorithms for computing the

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

✍ Xue, Guoliang 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

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 a