Searching a Hamiltonian Path in Giga-Node Graphs and Middle Levels Conjecture

概要

論文の詳細を見る
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.
2010-05-12