The Parity of Directed Hamiltonian Cycles
classification
💻 cs.DS
keywords
cycleshamiltonianalgorithmdirectednumberparitytimealgorithms
read the original abstract
We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619^n) time and polynomial space. For bipartite graphs, we give a 1.5^n poly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.