{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:01Z","timestamp":1759063741201},"reference-count":13,"publisher":"Wiley","issue":"8","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems & Computers in Japan"],"published-print":{"date-parts":[[1986,1]]},"abstract":"Abstract<\/jats:title>As suitable topology for interconnection networks of multiprocessors, De Bruijn graphs have been proposed and a number of investigations have been conducted on their fault tolerance. A De Bruijn graph is a directed graph with maximum degree d<\/jats:italic> (the maximum number of links that can be connected to one processor), diameter k<\/jats:italic> (maximum number of repeaters between two processors) and number of nodes d<\/jats:italic>k<\/jats:sup> (number of processors). A Kautz graph is a directed graph with maximum degree d<\/jats:italic>, diameter k<\/jats:italic> and number of nodes d<\/jats:italic>k<\/jats:sup> + d<\/jats:italic>k<\/jats:sup>\u20101. Both have the smallest diameter among the graphs with maximum degree d.<\/jats:italic> This paper proves the following: (1) If d<\/jats:italic> \u20102 nodes in a De Bruijn graph are removed (if d<\/jats:italic> \u20102 processors are faulty), its diameter becomes d<\/jats:italic> + 1, which is only 1 larger than the original diameter. (2) If d<\/jats:italic> \u20103 nodes in a Kautz graph are removed, its diameter becomes k<\/jats:italic> + 1 and if d<\/jats:italic> \u20101 nodes are removed, the diameter is k<\/jats:italic> + 2 or less, which is at most 2 larger than the original diameter. (3) The values of (1) and (2) are at most 1 larger than the lower bound under the limitation of degree d<\/jats:italic>, (4) A fault\u2010tolerant routing algorithm can be realized easily. This algorithm is better than any existing algorithm because of its short routes.<\/jats:p>","DOI":"10.1002\/scj.4690170803","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:27:57Z","timestamp":1183811277000},"page":"21-30","source":"Crossref","is-referenced-by-count":39,"title":["Fault\u2010tolerant processor interconnection networks"],"prefix":"10.1002","volume":"17","author":[{"given":"Makoto","family":"Imase","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Terunao","family":"Soneoka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keiji","family":"Okada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676295"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676101"},{"key":"e_1_2_1_4_2","unstructured":"U. D.KumarandS. M.Reddy. A class of graphs for fault\u2010tolerant processor interconnections Proc. 5th Int. Conf. Distributed Computing Systems' pp.137\u2013147(Oct.1984)."},{"key":"e_1_2_1_5_2","unstructured":"B.Elspas. Topological construction on interconnection limited logic Switching Circuit Theory and Logic Design pp.137\u2013147(Oct.1954)."},{"key":"e_1_2_1_6_2","first-page":"758","article-title":"A combinatorial problem","volume":"49","author":"De Bruijn","year":"1946","journal-title":"Koninklike Nederlandse Academie van Wetenscppen Proc. Ser."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675809"},{"key":"e_1_2_1_8_2","unstructured":"Kautz. Bounds on directed (d k)\u2010graphs In Theory of Cellular Logic Networks and Machines AFCRL\u201068\u20130668 WRI proj.7258 Final Report1968)."},{"key":"e_1_2_1_9_2","unstructured":"S. M.Reddy J. G.Kuhl S. H.HosseiniandH.Lee. On digraphs with minimum diameter and maximum connectivity Proc. 20th Annual Allerton Conf. on Commu. Cont. and Comput. pp.1018\u20131026(Oct.1982)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90076-X"},{"key":"e_1_2_1_11_2","first-page":"1","article-title":"Graphs and interconnection networks: Diameter and Vulnerability, Surveys in Combinatoriec","volume":"82","author":"Bermond J. C.","year":"1983","journal-title":"London Math. Soc. Lec. Notes Survey"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060215"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676455"},{"key":"e_1_2_1_14_2","first-page":"1","article-title":"Method of constructing a regular graph with a near\u2010minimum diameter","volume":"66","author":"Imase","year":"1983","journal-title":"Trans. I.E.C.E., Japan"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170803","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T05:54:45Z","timestamp":1697867685000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":13,"journal-issue":{"issue":"8","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170803"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170803","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}