{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T01:40:18Z","timestamp":1713318018973},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>Given an unreliable communication network, we seek a most reliable source (MRS) of the network, which maximizes the expected number of nodes that are reachable from it. The problem of computing an MRS in general graphs is #P-hard. However, this problem in tree networks has been solved in a linear time. A tree network has a weakness of low capability of failure tolerance. Embedding rings into it by adding some additional certain edges to it can enhance its failure tolerance, resulting in another class of sparse networks, called the ring-tree networks. This class of network also has an underlying tree-like topology, leading to its advantage of being easily administrated. This paper concerns with an important case whose underlying topology is a strip graph, called \u03bb\u2013rings network, and focuses on an unreliable \u03bb\u2013rings network where each link has an independent operational probability while all nodes are immune to failures. We apply the Divide-and-Conquer approach to design a fast algorithm for computing an MRS, and employ a binary division tree (BDT) to analyze its time complexity to be [Formula: see text].<\/jats:p>","DOI":"10.1142\/s1793830911001371","type":"journal-article","created":{"date-parts":[[2012,1,4]],"date-time":"2012-01-04T19:00:28Z","timestamp":1325703628000},"page":"503-516","source":"Crossref","is-referenced-by-count":3,"title":["A DIVIDE-AND-CONQUER ALGORITHM FOR FINDING A MOST RELIABLE SOURCE ON A RING-EMBEDDED TREE NETWORK WITH UNRELIABLE EDGES"],"prefix":"10.1142","volume":"03","author":[{"given":"WEI","family":"DING","sequence":"first","affiliation":[{"name":"Zhejiang Water Conservancy and Hydropower College, Hangzhou, Zhejiang, 310018, P. R. China"}]},{"given":"GUOLIANG","family":"XUE","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287-8809, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.1.18"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210306"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"rf4","volume-title":"The Combinatorics of Network Reliability","author":"Colbourn C. J.","year":"1987"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00124-2"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.003"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220303"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347478"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<219::AID-NET7>3.0.CO;2-L"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.13.2.85"},{"key":"rf13","first-page":"363","volume":"28","author":"Nel L. D.","journal-title":"INFOR"},{"key":"rf14","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198533863.001.0001","volume-title":"Network Reliability and Algebraic Structure","author":"Shier D. R.","year":"1991"},{"key":"rf15","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"2001"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199708)30:1<37::AID-NET5>3.0.CO;2-M"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830911001371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T01:05:43Z","timestamp":1713315943000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830911001371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":15,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1142\/S1793830911001371"],"URL":"https:\/\/doi.org\/10.1142\/s1793830911001371","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}