On the 2-MRS problem in a tree with unreliable edges
type: Item
instance of: scholarly article
title: On the 2-MRS problem in a tree with unreliable edges
zbMATH Open document ID: 1397.68140
DOI: 10.1155/2013/743908
author: Wei Ding
author: Yu Zhou
author: Guang-Ting Chen
author: Hongfa Wang
author: Guangming Wang
published in: Journal of Applied Mathematics
publication date: 2018-10-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68M10
zbMATH DE Number: 6950852
Wikidata QID: Q59004207
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/743908
OpenAlex ID: W2002665837
Recommended article: An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges
Recommended article: A single facility location problem on a tree with unreliable edges
Recommended article: On the location of a constrained \(k\)-tree facility in a tree network with unreliable edges
Recommended article: Q4355484
Recommended article: On minimal cost-reliability ratio spanning trees and related problems
Recommended article: Exact algorithms for bi-objective ring tree problems with reliability measures
Recommended article: On the random 2-stage minimum spanning tree
Recommended article: Q4425949
Recommended article: Two dependency constrained spanning tree problems
description: scientific article; zbMATH DE number 6950852