Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs
J Zhang - arXiv preprint arXiv:0812.1123, 2008 - arxiv.org
J Zhang
arXiv preprint arXiv:0812.1123, 2008•arxiv.orgWe propose an improved algorithm for counting the number of Hamiltonian cycles in a
directed graph. The basic idea of the method is sequential acceptance/rejection, which is
successfully used in approximating the number of perfect matchings in dense bipartite
graphs. As a consequence, a new bound on the number of Hamiltonian cycles in a directed
graph is proved, by using the ratio of the number of 1-factors. Based on this bound, we prove
that our algorithm runs in expected time of $ O (n^{8.5}) $ for dense problems. This improves …
directed graph. The basic idea of the method is sequential acceptance/rejection, which is
successfully used in approximating the number of perfect matchings in dense bipartite
graphs. As a consequence, a new bound on the number of Hamiltonian cycles in a directed
graph is proved, by using the ratio of the number of 1-factors. Based on this bound, we prove
that our algorithm runs in expected time of $ O (n^{8.5}) $ for dense problems. This improves …
We propose an improved algorithm for counting the number of Hamiltonian cycles in a directed graph. The basic idea of the method is sequential acceptance/rejection, which is successfully used in approximating the number of perfect matchings in dense bipartite graphs. As a consequence, a new bound on the number of Hamiltonian cycles in a directed graph is proved, by using the ratio of the number of 1-factors. Based on this bound, we prove that our algorithm runs in expected time of for dense problems. This improves the Markov chain method, the most powerful existing method, a factor of at least in running time. This class of dense problems is shown to be nontrivial in counting, in the sense that it is $#$P-Complete.
arxiv.org