{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T14:10:32Z","timestamp":1761487832789},"reference-count":11,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5215,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider a distributed processing system with a set <jats:italic>K<\/jats:italic> of sites that can either cooperate in computing a function or hold resources required by other sites. The system is implemented using a communication network with unreliable nodes. Two simplified reliability problems then arise. In the first problem, we are interested in computing the probability that every operational pair of sites in <jats:italic>K<\/jats:italic> can communicate with each other. This problem is known to be #P\u2010complete. In the second problem, the sites in <jats:italic>K<\/jats:italic> are service centers. Our reliability measure is the probability that every operational site in the network is connected to at least one operational service center. In this paper, we define the class of <jats:italic>t<\/jats:italic>\u2010polygon graphs, <jats:italic>t<\/jats:italic> \u2265 3, as the intersection graphs of straight\u2010line chords in a convex <jats:italic>t<\/jats:italic>\u2010gon. Hence, any <jats:italic>t<\/jats:italic>\u2010polygon graph is a circle graph. We show that both problems admit polynomial time solutions when the underlying graph of the network is restricted to a <jats:italic>t<\/jats:italic>\u2010polygon graph, for a fixed <jats:italic>t<\/jats:italic>.<\/jats:p>","DOI":"10.1002\/net.3230220405","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:21:37Z","timestamp":1178972497000},"page":"369-384","source":"Crossref","is-referenced-by-count":13,"title":["Algorithms for K\u2010terminal reliability problems with node failures"],"prefix":"10.1002","volume":"22","author":[{"given":"Ehab S.","family":"Elmallah","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200706"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100206"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603016"},{"key":"e_1_2_1_5_2","volume-title":"The Combinatorics of Network Reliability","author":"Colbourn C. J.","year":"1987"},{"key":"e_1_2_1_6_2","article-title":"Computing residual connectedness reliability for restricted networks","author":"Colbourn C. J.","journal-title":"Discrete Appl. Math."},{"key":"e_1_2_1_7_2","article-title":"Independence and domination in polygon graphs","author":"Elmallah E. S.","journal-title":"Discrete Math."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"C. P.Gabor W.Hsu andK. J.Supowit Recognizing circle graphs in polynomial time.26th IEEE Symposium on Foundations of Computer Science(1985)106\u2013116.","DOI":"10.1109\/SFCS.1985.47"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215050"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0220009"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220405","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T11:13:46Z","timestamp":1698059626000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220405"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["10.1002\/net.3230220405"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220405","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}