研究者情報 | 神奈川大学

ボサール　アントワーヌ Antoine Bossard ボサール　アントワーヌ所属神奈川大学情報学部計算機科学科神奈川大学大学院理学研究科理学専攻（情報科学領域）職種教授
言語種別	英語
発行・発表の年月	2018/11
形態種別	学術雑誌
査読	査読あり
標題	Torus pairwise disjoint-path routing
執筆形態	共著
掲載誌名	Sensors
掲載区分	国外
出版社・発行元	MDPI
巻・号・頁	18(11),pp.3912
著者・共著者	A. Bossard, K. Kaneko
概要	[Full paper] [WoS SCIE, 2021: WoS IF=3.847, WoS Q2] Modern supercomputers include hundreds of thousands of processors. The interconnection network is in charge of mutually connecting these processors. Tori have become a popular interconnect topology. We address the pairwise disjoint-path routing problem in a torus, which consists of the selection of mutually vertex disjoint paths between given vertex pairs. Its solution has critical implications, like increased system dependability and more efficient data transfers, and provides concrete implementation of green and sustainable computing as well as security, privacy, and trust, e.g. for the Internet of Things. The correctness and complexities of the proposed algorithm are formally established. In an n-dimensional k-ary torus (n<k, k>=5), the algorithm connects c (c<=n) vertex pairs with mutually vertex-disjoint paths of lengths at most 2k(c-1) + n\lfloor k/2\rfloor, and the worst-case time complexity of the algorithm is O(nc^4).