Back to Search
Start Over
An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges.
- Source :
- Asia-Pacific Journal of Operational Research; Feb2015, Vol. 32 Issue 1, p-1, 17p
- Publication Year :
- 2015
-
Abstract
- The sum-max 2-most reliable sources (Sum-Max 2-MRS) problem in a given unreliable network is referred to as finding a pair of nodes in the network from which the expected number of reachable nodes is maximized. This problem is #P-hard on general graphs and admits a cubic time algorithm on trees with unreliable edges. In this paper, we revisit the problem on trees and design an edge-turbulence algorithm with a quadratic time and quadratic spaces. Finally, we further develop an edge-turbulence based parallel algorithm with a lower time complexity. [ABSTRACT FROM AUTHOR]
- Subjects :
- TURBULENCE
ALGORITHMS
GRAPH theory
COMPLEXITY (Philosophy)
PROBLEM solving
Subjects
Details
- Language :
- English
- ISSN :
- 02175959
- Volume :
- 32
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Asia-Pacific Journal of Operational Research
- Publication Type :
- Academic Journal
- Accession number :
- 100927998
- Full Text :
- https://doi.org/10.1142/S0217595915400102