کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435525 689912 2011 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
چکیده انگلیسی

Given an unreliable communication network, we seek for a node which maximizes the expected number of nodes that are reachable from it. Such a node is called a most reliable source (MRS) of the network. In communication networks, failures may occur to both links and nodes. Previous studies have considered the case where each link has an independent operational probability, while the nodes are immune to failures. In practice, however, failures may happen to the nodes as well, including both transmitting fault and receiving fault. Recently, another variant of the MRS problem is studied, where all links are immune to failures and each node has an independent transmitting probability and receiving probability, and an O(n2) time algorithm is presented for computing an MRS on tree networks with n nodes. In this paper, we present a faster algorithm for this problem, with a time complexity of O(n).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 3, 21 January 2011, Pages 225-232