2009 | OriginalPaper | Buchkapitel
A Linear Time Algorithm for Computing the Most Reliable Source on a Tree with Faulty Vertices
verfasst von : Wei Ding, Guoliang Xue
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given an unreliable communication network, we seek for determining a vertex from the network, the expected number of vertices which connects to is maximum. Such vertex is named the most reliable source (MRS) on the network. The communication failures may occur to links or vertices of the network. The case was generally studied, where no failure happens to each vertex and each link has an independent operational probability. Practically, failures frequently happen to the vertices, including the transmitting fault and receiving fault. Recently, another case is proposed, where each link is steady and each vertex has an independent transmitting probability and receiving probability, and an
$\mathcal{O}(n^2)$
time algorithm is presented for computing the MRS on such tree networks with
n
vertices. In this paper, we propose a faster algorithm for this case, whose time complexity is
$\mathcal{O}(n)$
.