An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges

Yu Zhou (), Wei Ding (), Guangming Wang () and Guangting Chen ()
Additional contact information
Yu Zhou: School of Science, Hangzhou Dianzi University, Hangzhou, Zhejiang, 310018, P. R. China
Wei Ding: Zhejiang University of Water Resources and Electric Power, Hangzhou, Zhejiang 310018, P. R. China
Guangming Wang: School of Science, Hangzhou Dianzi University, Hangzhou, Zhejiang, 310018, P. R. China
Guangting Chen: Taizhou University, Linhai, Zhejiang, 317000, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 01, 1-17

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.

Keywords: Sum-Max 2-MRS; the edge-turbulence algorithm; quadratic time (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915400102
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:32:y:2015:i:01:n:s0217595915400102

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915400102

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().