Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs

Details Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs

2008-12-05

arxiv.org/abs/0812.1123v4

Computer Science

Data Structures and Algorithms

20 pages

Scientific paper

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 $O(n^{8.5})$ for dense problems. This improves the Markov chain method, the most powerful existing method, a factor of at least $n^{4.5}(\log n)^{4}$ in running time. This class of dense problems is shown to be nontrivial in counting, in the sense that it is $#$P-Complete.

Affiliated with

Also associated with

No associations

Rating

Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-365549