研究者情報 | 神奈川大学

ボサール　アントワーヌ Antoine Bossard ボサール　アントワーヌ所属神奈川大学情報学部計算機科学科神奈川大学大学院理学研究科理学専攻（情報科学領域）職種教授
言語種別	英語
発行・発表の年月	2023/01
形態種別	学術雑誌
査読	査読あり
標題	On the crossing number of a torus network
執筆形態	共著
掲載誌名	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
掲載区分	国内
出版社・発行元	IEICE
巻・号・頁	E106-A(1),pp.35-44
著者・共著者	A. Bossard, K. Kaneko and F. C. Harris, Jr.
概要	[Full paper] [WoS SCIE, 2021: WoS IF=0.423, WoS Q4] Reducing the number of link crossings in a network drawn on the plane such as a wiring board is a well-known problem, and especially the calculation of the minimum number of such crossings: this is the crossing number problem and it is NP-hard. We address it for particular classes of graphs: tori. First, we discuss an upper bound on cr(T(2, k)) the number of crossings in a 2-dimensional k-ary torus T(2, k) where k>=2. Second, we derive an upper bound on the crossing number of a 3-dimensional k-ary torus: cr(T(3, k)) <= cr(T(3, k)) \leq 2k^4 - k^3 - 4k^2 - 2\lceil k/2\rceil\lfloor k/2\rfloor(k - (k mod 2)) is obtained. Third, an upper bound on the crossing number of an n-dimensional k-ary torus is derived from the previously established results, with the order of this upper bound additionally established for more clarity: cr(T(n, k)) is O(n^2 k^{2n-2}) when n>=k and O(nk^{2n-1}) otherwise.