Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Enumerating all Hamilton Cycles and Bounding the Number of Hamilton Cycles in 3-Regular Graphs. | Enumerating all Hamilton Cycles and Bounding the Number of Hamilton Cycles in 3-Regular Graphs Heidi Gebauer Institute of Theoretical Computer Science ETH Zurich CH-8092 Zurich Switzerland gebauerh@ Submitted Sep 22 2009 Accepted Jun 10 2011 Published Jun 21 2011 Mathematics Subject Classifications 05C35 05C45 05C85 Abstract We describe an algorithm which enumerates all Hamilton cycles of a given 3-regular n-vertex graph in time O improving on Eppstein s previous bound. The resulting new upper bound of O for the maximum number of Hamilton cycles in 3-regular n-vertex graphs gets close to the best known lower bound of Q . Our method differs from Eppstein s in that he considers in each step a new graph and modifies it while we fix at the very beginning one Hamilton cycle C and then proceed around C successively producing partial Hamilton cycles. 1 Introduction The famous traveling salesman problem TSP is one of the most fundamental NP-complete graph problems 4 . For decades the best known algorithm for TSP was the dynamic programming algorithm by Held and Karp 6 which runs in time O 2n with n denoting the number of vertices of the given graph. This was also the strongest known upper bound for the subproblem of deciding whether a given graph contains a Hamilton cycle. In a recent breakthrough Bjorklund 2 gave a Monte Carlo algorithm for detecting whether a given graph contains a Hamilton cycle or not which runs in time n with false positives and false negatives occurring with probability exponentially small in n. We let poly n denote a polynomial factor in n. For bipartite graphs this algorithm even runs in time 22 poly n . Despite this major development it is still open whether the traveling salesman problem in its general form can be solved in time O 9 . Therefore it is of interest to consider some restricted problem classes which - while still NP-complete - might be treated faster. An extended abstract appeared in
