On the 2-MRS Problem in a Tree with Unreliable Edges

Abstract EN

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.