{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T05:04:11Z","timestamp":1698037451524},"reference-count":9,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T00:00:00Z","timestamp":1188950400000},"content-version":"vor","delay-in-days":6456,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1990,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Torus is one of the most promising interconnection topologies for multiprocessor systems with a large number of processors. This paper presents a parallel branch\u2010and\u2010bound algorithm for a torus machine with additional global links. Using the torus network, processors send subproblems to adjacent processors to balance their loads. Global links are used for broadcasting the newly obtained temporary solution to all processors. Using simulation experiments, the performance of the proposed algorithm was compared with that of another algorithm implemented on an improved tree machine called the DON system. These experiments showed that the speed\u2010up rate obtained by the proposed algorithm is always greater than the speed\u2010up rate obtained by the algorithm implemented on the DON system.<\/jats:p>","DOI":"10.1002\/scj.4690210311","type":"journal-article","created":{"date-parts":[[2009,11,19]],"date-time":"2009-11-19T23:17:18Z","timestamp":1258672638000},"page":"101-108","source":"Crossref","is-referenced-by-count":0,"title":["A Parallel Branch\u2010and\u2010Bound Algorithm for a Torus Machine"],"prefix":"10.1002","volume":"21","author":[{"given":"Tsuyoshi","family":"Kawaguchi","sequence":"first","affiliation":[]},{"given":"Tamotsu","family":"Maeda","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,9,6]]},"reference":[{"key":"e_1_2_1_2_2","series-title":"Mathematical Programming Series, 8","volume-title":"Combinatorial Optimization","author":"Ibaraki T.","year":"1984"},{"issue":"6","key":"e_1_2_1_3_2","first-page":"403","article-title":"A parallelized branch\u2010and\u2010bound algorithm: Implementation and efficiency","volume":"62","author":"Imai M.","year":"1979","journal-title":"Trans. I.E.C.E., Japan"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676453"},{"key":"e_1_2_1_5_2","unstructured":"A.ItoandH.Kasahara Parallel processing of optimal multiprocessor scheduling algorithm. The 34th National Convention of Information Processing Society of Japan pp.273\u2013274(1987)."},{"issue":"9","key":"e_1_2_1_6_2","first-page":"1002","article-title":"A double\u2010tree structured multicomputer system and its application to combinatorial problems","volume":"69","author":"Imai M.","year":"1986","journal-title":"Trans. I.E.C.E., Japan"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"O.Vornbeger Implementing branch\u2010and\u2010bound in a ring of processors. CONPAR 86 Proc. Conf. on Algorithms and Hardware for Parallel Processing Aachen pp.157\u2013164(1986).","DOI":"10.1007\/3-540-16811-7_166"},{"key":"e_1_2_1_8_2","volume-title":"Design of Parallel Computers","author":"Tomita S.","year":"1986"},{"key":"e_1_2_1_9_2","unstructured":"T.Maeda T.Kawaguchi andS.Kyan Parallel execution scheme of Prolog programs on a torus machine. The 38th National Convention of Information Processing Society of Japan pp.1500\u20131501(1989)."},{"key":"e_1_2_1_10_2","unstructured":"T.MaedaandK.Kawaguchi Parallel execution scheme of Prolog programs on a torus machine. Proc. of China 1989 Int. Conf. Circuits and Systems Nanjing China (July1989)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690210311","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690210311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T20:27:50Z","timestamp":1698006470000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690210311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,1]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,1]]}},"alternative-id":["10.1002\/scj.4690210311"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690210311","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,1]]}}}