研究者情報 | 神奈川大学

ボサール　アントワーヌ Antoine Bossard ボサール　アントワーヌ所属神奈川大学情報学部計算機科学科神奈川大学大学院理学研究科理学専攻（情報科学領域）職種教授
言語種別	英語
発行・発表の年月	2022/07
形態種別	学術雑誌
査読	査読あり
標題	Set-to-Set Disjoint Path Routing in Bijective Connection Graphs
執筆形態	共著
掲載誌名	IEEE Access
掲載区分	国外
巻・号・頁	10,pp.72731-72742
著者・共著者	K. Kaneko, A. Bossard, F. C. Harris, Jr.
概要	[Full paper] [WoS SCIE, 2021: WoS IF=3.476, WoS Q2] The bijective connection graph encompasses a family of cube-based topologies, and n-dimensional bijective connection graphs include the hypercube and almost all of its variants with the order 2^n and the degree n. The set-to-set disjoint paths problem is as follows: for a set of source nodes S={s1,s2,...,sp} and destination nodes D={d1,d2,...,dp} in a k-connected graph with p<=k, find p paths Pi: si~>d{ji} (1<=i<=p) such that {j1,j2,...,jp}={1,2,...,p} and the paths Pi are node-disjoint. This is an important issue in parallel and distributed computing. We propose an algorithm that constructs p (<=n) disjoint paths between any pair of node sets in n-dimensional bijective connection graphs in polynomial-order time of n: the time complexity is O(n^3p^4) and the maximum path length n+p-1. According to a computer experiment in a locally twisted cube, the average time complexity is O(n^2),and the average maximum path is 0.6333n-0.266.
DOI	10.1109/ACCESS.2022.3188783