On the 2-MRS Problem in a Tree with Unreliable Edges. (12th November 2013)

• Record Type: Journal Article
• Authors: Ding, Wei; Zhou, Yu; Chen, Guangting; Wang, Hongfa; Wang, Guangming
• Other Names: Choi Han H. Academic Editor.
• Is Part Of: Journal of applied mathematics. Volume 2013(2013)
• Publication Date: 2013-11-12
• Subjects: Mathematics -- Periodicals; 519.05
• DOI: 10.1155/2013/743908
• Languages: English
• ISSNs: 1110-757X

Abstract

Abstract : This paper extends the well-known most reliable source (1-MRS) problem in unreliable graphs to the 2-most reliable source (2-MRS) problem. Two kinds of reachable probability models of node pair in unreliable graphs are considered, that is, the superior probability and united probability. The 2-MRS problem aims to find a node pair in the graph from which the expected number of reachable nodes or the minimum reachability is maximized. It has many important applications in large-scale unreliable computer or communication networks. The #P-hardness of the 2-MRS problem in general graphs follows directly from that of the 1-MRS problem. This paper deals with four models of the 2-MRS problem in unreliable trees where every edge has an independent working probability and devises a cubic-time and quadratic-space dynamic programming algorithm, respectively, for each model.