2024-04-18T01:48:57Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000693272024-03-29T05:26:34Z01164:02592:05970:06096
Searching a Hamiltonian Path in Giga-Node Graphs and Middle Levels ConjectureSearching a Hamiltonian Path in Giga-Node Graphs and Middle Levels Conjectureenghttp://id.nii.ac.jp/1001/00069327/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=69327&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of JapanDept. of Computer Science, Gunma UniversityDept. of Computer Science, Gunma UniversityManabu, ShimadaKazuyuki, AmanoThe middle levels conjecture asserts that there is a Hamiltonian cycle in the middle two levels of 2k+1-dimensional hypercube. The conjecture is known to be true for k ≤ 17 [I. Shields, B.J. Shields and C.D. Savage, Disc. Math., 309, 5271–5277 (2009)]. In this note, we verify that the conjecture is also true for k = 18 and 19 by constructing a Hamiltonian cycle in the middle two levels of 37- and 39-dimensional hypercube with the aid of the computer. We achieve this by introducing a new decomposition technique and an efficient algorithm for ordering the Narayana objects. In the largest case, our program could find a Hamiltonian path in a graph with ～ 1.18 × 10⁹ nodes in about 80 days on a standard PC.The middle levels conjecture asserts that there is a Hamiltonian cycle in the middle two levels of 2k+1-dimensional hypercube. The conjecture is known to be true for k ≤ 17 [I. Shields, B.J. Shields and C.D. Savage, Disc. Math., 309, 5271–5277 (2009)]. In this note, we verify that the conjecture is also true for k = 18 and 19 by constructing a Hamiltonian cycle in the middle two levels of 37- and 39-dimensional hypercube with the aid of the computer. We achieve this by introducing a new decomposition technique and an efficient algorithm for ordering the Narayana objects. In the largest case, our program could find a Hamiltonian path in a graph with ～ 1.18 × 10⁹ nodes in about 80 days on a standard PC.AN1009593X研究報告アルゴリズム（AL）2010-AL-1309162010-05-122010-04-27