http://swrc.ontoware.org/ontology#TechnicalReport
Searching a Hamiltonian Path in Giga-Node Graphs and Middle Levels Conjecture
en
Dept. of Computer Science, Gunma University
Dept. of Computer Science, Gunma University
Manabu Shimada
Kazuyuki Amano
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.
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-130
9
1-6
2010-05-12