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

Wei Ding | Zendy; Yu Zhou | Zendy; Guangting Chen | Zendy; Hongfa Wang | Zendy; Guangming Wang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Wei Ding,

Yu Zhou,

Guangting Chen,

Hongfa Wang,

Guangming Wang

Publication year - 2013

Publication title -

journal of applied mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.307

H-Index - 43

eISSN - 1687-0042

pISSN - 1110-757X

DOI - 10.1155/2013/743908

Subject(s) - reachability , node (physics) , enhanced data rates for gsm evolution , tree (set theory) , computer science , mathematics , quadratic equation , graph , combinatorics , mathematical optimization , discrete mathematics , artificial intelligence , geometry , structural engineering , engineering

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research