{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:42:58Z","timestamp":1740134578318,"version":"3.37.3"},"reference-count":21,"publisher":"Wiley","license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Applied Mathematics"],"published-print":{"date-parts":[[2013]]},"abstract":"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.<\/jats:p>","DOI":"10.1155\/2013\/743908","type":"journal-article","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T16:11:12Z","timestamp":1384272672000},"page":"1-11","source":"Crossref","is-referenced-by-count":2,"title":["On the 2-MRS Problem in a Tree with Unreliable Edges"],"prefix":"10.1155","volume":"2013","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4353-5385","authenticated-orcid":true,"given":"Wei","family":"Ding","sequence":"first","affiliation":[{"name":"Zhejiang University of Water Resources and Electric Power, Hangzhou, Zhejiang 310018, China"}]},{"given":"Yu","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Science, Hangzhou Dianzi University, Hangzhou, Zhejiang 310018, China"}]},{"given":"Guangting","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, Hangzhou, Zhejiang 310018, China"}]},{"given":"Hongfa","family":"Wang","sequence":"additional","affiliation":[{"name":"Zhejiang University of Water Resources and Electric Power, Hangzhou, Zhejiang 310018, China"}]},{"given":"Guangming","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Science, Hangzhou Dianzi University, Hangzhou, Zhejiang 310018, China"}]}],"member":"311","reference":[{"year":"1976","key":"4"},{"year":"1996","key":"22"},{"year":"1987","series-title":"International Series of Monographs on Computer Science","key":"5"},{"year":"1991","series-title":"Oxford Science Publications","key":"21"},{"issue":"1","key":"1","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1287\/opre.41.1.18","volume":"41","year":"1993","journal-title":"Operations Research"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210306"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00124-2"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.003"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830911001371"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22616-8_9"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220303"},{"issue":"3","key":"13","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1287\/trsc.31.3.216","volume":"31","year":"1997","journal-title":"Transportation Science"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<219::AID-NET7>3.3.CO;2-K"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.13.2.85"},{"volume":"28","year":"1990","key":"18"},{"key":"19","doi-asserted-by":"publisher","DOI":"10.1007\/BF03024856"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.02.007"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199708)30:1<37::AID-NET5>3.0.CO;2-M"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.61"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2013.30"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.02.005"}],"container-title":["Journal of Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/jam\/2013\/743908.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/jam\/2013\/743908.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/jam\/2013\/743908.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,21]],"date-time":"2017-06-21T21:50:28Z","timestamp":1498081828000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.hindawi.com\/journals\/jam\/2013\/743908\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"references-count":21,"alternative-id":["743908","743908"],"URL":"https:\/\/doi.org\/10.1155\/2013\/743908","relation":{},"ISSN":["1110-757X","1687-0042"],"issn-type":[{"type":"print","value":"1110-757X"},{"type":"electronic","value":"1687-0042"}],"subject":[],"published":{"date-parts":[[2013]]}}}