{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T03:34:18Z","timestamp":1768016058400,"version":"3.49.0"},"reference-count":0,"publisher":"Wiley","issue":"29","license":[{"start":{"date-parts":[[2004,7,7]],"date-time":"2004-07-07T00:00:00Z","timestamp":1089158400000},"content-version":"vor","delay-in-days":188,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["International Journal of Mathematics and Mathematical Sciences"],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>, <jats:italic>E<\/jats:italic>) be a graph with a distinguished set of terminal\nvertices <jats:italic>K<\/jats:italic>\u2ac5<jats:italic>V<\/jats:italic>. We define the <jats:italic>K<\/jats:italic>\u2010diameter of <jats:italic>G<\/jats:italic> as\nthe maximum distance between any pair of vertices of <jats:italic>K<\/jats:italic>. If the\nedges fail randomly and independently with known probabilities\n(vertices are always operational), the\n<jats:italic>diameter-constrained K-terminal reliability<\/jats:italic> of <jats:italic>G<\/jats:italic>,\n<jats:italic>R<\/jats:italic><jats:sub><jats:italic>K<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>, <jats:italic>D<\/jats:italic>), is defined as the probability that surviving edges\nspan a subgraph whose <jats:italic>K<\/jats:italic>\u2010diameter does not exceed <jats:italic>D<\/jats:italic>. In general, the computational complexity\nof evaluating <jats:italic>R<\/jats:italic><jats:sub><jats:italic>K<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>, <jats:italic>D<\/jats:italic>) is NP\u2010hard, as this measure subsumes the\nclassical <jats:italic>K<\/jats:italic>\u2010terminal reliability <jats:italic>R<\/jats:italic><jats:sub><jats:italic>K<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>), known to belong to\nthis complexity class. In this note, we show that even though for\ntwo terminal vertices <jats:italic>s<\/jats:italic> and <jats:italic>t<\/jats:italic>\n and <jats:italic>D<\/jats:italic> = 2, <jats:italic>R<\/jats:italic><jats:sub>{<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>}<\/jats:sub>(<jats:italic>G<\/jats:italic>, <jats:italic>D<\/jats:italic>)\n\ncan be determined in polynomial time, the problem of calculating\n<jats:italic>R<\/jats:italic><jats:sub>{<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>}<\/jats:sub>(<jats:italic>G<\/jats:italic>, <jats:italic>D<\/jats:italic>) for fixed values of <jats:italic>D<\/jats:italic>, <jats:italic>D<\/jats:italic> \u2265 3, is\nNP\u2010hard. We also generalize this result for any fixed number of\nterminal vertices. Although it is very unlikely that general\nefficient algorithms exist, we present a recursive formulation\nfor the calculation of <jats:italic>R<\/jats:italic><jats:sub>{<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>}<\/jats:sub>(<jats:italic>G<\/jats:italic>, <jats:italic>D<\/jats:italic>) that yields a\npolynomial time evaluation algorithm in the case of complete\ntopologies where the edge set can be partitioned into at most\nfour equi\u2010reliable classes.<\/jats:p>","DOI":"10.1155\/s016117120430623x","type":"journal-article","created":{"date-parts":[[2004,7,7]],"date-time":"2004-07-07T18:07:26Z","timestamp":1089223646000},"page":"1551-1562","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Reliability of communication networks with delay constraints: computational complexity and complete topologies"],"prefix":"10.1155","volume":"2004","author":[{"given":"H.","family":"Cancela","sequence":"first","affiliation":[]},{"given":"L.","family":"Petingi","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,7,7]]},"container-title":["International Journal of Mathematics and Mathematical Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijmms\/2004\/314763.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijmms\/2004\/314763.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/S016117120430623X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,27]],"date-time":"2024-06-27T13:44:24Z","timestamp":1719495864000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/S016117120430623X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":0,"journal-issue":{"issue":"29","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1155\/S016117120430623X"],"URL":"https:\/\/doi.org\/10.1155\/s016117120430623x","archive":["Portico"],"relation":{},"ISSN":["0161-1712","1687-0425"],"issn-type":[{"value":"0161-1712","type":"print"},{"value":"1687-0425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]},"assertion":[{"value":"2003-06-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2004-07-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}