{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T15:13:19Z","timestamp":1769008399222,"version":"3.49.0"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1997,6]]},"abstract":"<jats:p> The capability of fault tolerance is one of the advantages of multiprocessor systems. In this paper, we prove that the fault tolerance of an n-star graph is 2n-5 with restriction to the forbidden faulty set. And we propose an algorithm for examining the connectivity of an n-star graph when there exist at most 2n - 4 faults. The algorithm requires O(n<jats:sup>2<\/jats:sup> log n) time. Besides, we improve the fault-tolerant routing algorithm proposed by Bagherzadeh et al. by calculating the cycle structure of a permutation and the avoidance of routing message to a node without any nonfaulty neighbor. This calculation needs only constant time. And then, we propose an efficient fault-tolerant broadcasting algorithm. When there is no fault, our broadcasting algorithm remains optimal. The penalty is O(n) if there exists only one fault, and the penalty is O(n<jats:sup>2<\/jats:sup>) if there exist at most n - 2 faults. <\/jats:p>","DOI":"10.1142\/s0129054197000112","type":"journal-article","created":{"date-parts":[[2003,10,15]],"date-time":"2003-10-15T20:35:19Z","timestamp":1066250119000},"page":"127-142","source":"Crossref","is-referenced-by-count":14,"title":["Fault Tolerance on Star Graphs"],"prefix":"10.1142","volume":"08","author":[{"given":"Shuo-Cheng","family":"Hu","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 804, R.O.C."}]},{"given":"Chang-Biau","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 804, R.O.C."}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054197000112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:45:54Z","timestamp":1565124354000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054197000112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1997,6]]}},"alternative-id":["10.1142\/S0129054197000112"],"URL":"https:\/\/doi.org\/10.1142\/s0129054197000112","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,6]]}}}