On the 2-MRS problem in a tree with unreliable edges (Q1790110): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q59004207, #quickstatements; #temporary_batch_1706364719135 |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1155/2013/743908 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2002665837 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 21:11, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the 2-MRS problem in a tree with unreliable edges |
scientific article |
Statements
On the 2-MRS problem in a tree with unreliable edges (English)
0 references
10 October 2018
0 references
Summary: 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.
0 references