{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:57:45Z","timestamp":1774799865475,"version":"3.50.1"},"reference-count":29,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2018,11,13]],"date-time":"2018-11-13T00:00:00Z","timestamp":1542067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science and Technology","doi-asserted-by":"publisher","award":["17K00093"],"award-info":[{"award-number":["17K00093"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Modern supercomputers include hundreds of thousands of processors and they are thus massively parallel systems. The interconnection network of a system is in charge of mutually connecting these processors. Recently, the torus has become a very popular interconnection network topology. For example, the Fujitsu K, IBM Blue Gene\/L, IBM Blue Gene\/P, and Cray Titan supercomputers all rely on this topology. The pairwise disjoint-path routing problem in a torus network is addressed in this paper. This fundamental problem consists of the selection of mutually vertex disjoint paths between given vertex pairs. Proposing a solution to this problem has critical implications, such as increased system dependability and more efficient data transfers, and provides concrete implementation of green and sustainable computing as well as security, privacy, and trust, for instance, for the Internet of Things (IoT). Then, the correctness and complexities of the proposed routing algorithm are formally established. Precisely, in an n-dimensional k-ary torus (    n &lt; k    ,     k \u2265 5    ), the proposed algorithm connects c (    c \u2264 n    ) vertex pairs with mutually vertex-disjoint paths of lengths at most     2 k ( c \u2212 1 ) + n \u230a k \/ 2 \u230b    , and the worst-case time complexity of the algorithm is     O ( n  c 4  )    . Finally, empirical evaluation of the proposed algorithm is conducted in order to inspect its practical behavior.<\/jats:p>","DOI":"10.3390\/s18113912","type":"journal-article","created":{"date-parts":[[2018,11,14]],"date-time":"2018-11-14T10:58:22Z","timestamp":1542193102000},"page":"3912","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Torus Pairwise Disjoint-Path Routing"],"prefix":"10.3390","volume":"18","author":[{"given":"Antoine","family":"Bossard","sequence":"first","affiliation":[{"name":"Graduate School of Science, Kanagawa University, Kanagawa 259-1293, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keiichi","family":"Kaneko","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Tokyo University of Agriculture and Technology, Tokyo 184-8588, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,11,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/2465.2467","article-title":"The cosmic cube","volume":"28","author":"Seitz","year":"1985","journal-title":"Commun. ACM"},{"key":"ref_2","unstructured":"Meritt, R. (2018, September 27). Cray Studies Exascale Computing in Europe. Available online: http:\/\/www.eetimes.com\/document.asp?doc_id=1268565."},{"key":"ref_3","unstructured":"TOP500 Team (2018, September 27). TOP500 list refreshed, US Edged Out of Third Place. Available online: https:\/\/www.top500.org\/news\/top500-list-refreshed-us-edged-out-of-third-place\/."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1023\/B:SUPE.0000014803.83151.dc","article-title":"Efficient collective communications in dual-cube","volume":"28","author":"Li","year":"2004","journal-title":"J. Supercomput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s11227-009-0297-2","article-title":"Metacube\u2014A versatile family of interconnection networks for extremely large-scale supercomputers","volume":"53","author":"Li","year":"2010","journal-title":"J. Supercomput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","article-title":"A group-theoretic model for symmetric interconnection networks","volume":"C-38","author":"Akers","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","article-title":"Bounds for sorting by prefix reversal","volume":"27","author":"Gates","year":"1979","journal-title":"Discret. Math."},{"key":"ref_8","unstructured":"Duato, J., Yalamanchili, S., and Ni, L. (2003). Interconnection Networks: An Engineering Approach, Morgan Kaufmann."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Bossard, A., and Kaneko, K. (August, January 30). On the torus pairwise disjoint-path routing problem. Proceedings of the 18th IEEE International Conference on Computer and Information Technology (CIT), Halifax, NS, Canada.","DOI":"10.3390\/s18113912"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/MM.2011.98","article-title":"The Tofu interconnect","volume":"32","author":"Ajima","year":"2012","journal-title":"IEEE Micro"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ajima, Y., Inoue, T., Hiramoto, S., Uno, S., Sumimoto, S., Miura, K., Shida, N., Kawashima, T., Okamoto, T., and Moriyama, O. (2014, January 22\u201326). Tofu interconnect 2: System-on-chip integration of high-performance interconnect. Proceedings of the 29th International Supercomputing Conference, Leipzig, Germany.","DOI":"10.1007\/978-3-319-07518-1_35"},{"key":"ref_12","unstructured":"Cray Inc (2018, September 27). Cray XE6 Brochure. Available online: http:\/\/www.cray.com\/products\/computing\/xe-series."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MITP.2008.10","article-title":"Harnessing green IT: Principles and practices","volume":"10","author":"Murugesan","year":"2008","journal-title":"IT Prof."},{"key":"ref_14","unstructured":"Green500 (2018, September 27). June 2017 list. Available online: https:\/\/www.top500.org\/green500\/."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","article-title":"Zur allgemeinen Kurventheorie","volume":"10","author":"Menger","year":"1927","journal-title":"Fund. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","article-title":"On the complexity of combinatorial problems","volume":"5","author":"Karp","year":"1975","journal-title":"Networks"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","article-title":"Graph minors. XIII. The disjoint paths problem","volume":"63","author":"Robertson","year":"1995","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0020-0190(92)90113-A","article-title":"Optimal routing in toroidal networks","volume":"43","author":"Jerebic","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"ref_19","first-page":"162","article-title":"Fault tolerant routing in toroidal networks","volume":"E79-D","author":"Gu","year":"1996","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_20","first-page":"173","article-title":"A set-to-set disjoint paths routing algorithm in tori","volume":"7","author":"Kaneko","year":"2017","journal-title":"Int. J. Netw. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1006\/jpdc.2000.1632","article-title":"An efficient algorithm for the k-pairwise disjoint paths problem in hypercubes","volume":"60","author":"Gu","year":"2000","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(98)00121-5","article-title":"An efficient algorithm for k-pairwise disjoint paths in star graphs","volume":"67","author":"Gu","year":"1998","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/s11227-013-1013-9","article-title":"k-pairwise disjoint paths routing in perfect hierarchical hypercubes","volume":"67","author":"Bossard","year":"2014","journal-title":"J. Supercomput."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Sawada, N., Kaneko, K., and Peng, S. (2007, January 3\u20136). Pairwise disjoint paths in pancake graphs. Proceedings of the 8th International Conference on Parallel and Distributed Computing, Applications and Technologies, Adelaide, Australia.","DOI":"10.1109\/PDCAT.2007.4420193"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.tcs.2016.04.007","article-title":"Paired many-to-many disjoint path covers in restricted hypercube-like graphs","volume":"634","author":"Park","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.tcs.2015.09.022","article-title":"An efficient algorithm to construct disjoint path covers of DCell networks","volume":"609","author":"Wang","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1007\/s11227-013-0883-1","article-title":"Parallel construction of independent spanning trees and an application in diagnosis on M\u00f6bius cubes","volume":"65","author":"Cheng","year":"2013","journal-title":"J. Supercomput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1515\/jaiscr-2018-0016","article-title":"On the topological properties of the certain neural networks","volume":"8","author":"Liu","year":"2018","journal-title":"J. Artif. Intell. Soft Comput. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1515\/jaiscr-2018-0020","article-title":"The least eigenvalue of the graphs whose complements are connected and have pendent paths","volume":"8","author":"Wang","year":"2018","journal-title":"J. Artif. Intell. Soft Comput. Res."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/11\/3912\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:29:30Z","timestamp":1760196570000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/11\/3912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,13]]},"references-count":29,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2018,11]]}},"alternative-id":["s18113912"],"URL":"https:\/\/doi.org\/10.3390\/s18113912","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,13]]}}}