Numerical Parallel Approach to Counting Hamiltonian Cycles with Proth Primes
Koichi Kubota · Procedia Computer Science · 2013
Counting the number of Hamiltonian cycles of a given graph can be formulated with higher order derivatives. Thus its value can be computed as the residue with complex floating numbers. But there are inevitable rounding errors in the conventional computation of the residue whereas the mathematical result is an integer value. In this paper, by use of the Proth primes that are represented by k · 2n + 1 for odd number k, algorithms of the residue with modular arithmetics are proposed in order to compute the exact integer result. It is shown that they are naturally executed on parallel processors by partitioning the summation of the residue, so that, with q (≤ 2n) processors, the time complexity is O(n32n/q) for each machine and O(log q) for summing up all the q partial sums.