Editing Hamiltonian path problem (section)

=== Monte Carlo ===
Andreas Björklund provided an alternative approach using the [[inclusion–exclusion principle]] to reduce the problem of counting the number of Hamiltonian cycles to a simpler counting problem, of counting cycle covers, which can be solved by computing certain matrix determinants. Using this method, he showed how to solve the Hamiltonian cycle problem in arbitrary ''n''-vertex graphs by a [[Monte Carlo algorithm]] in time O(1.657<sup>''n''</sup>); for [[bipartite graph]]s this algorithm can be further improved to time [[Big O notation#Little-o notation|O]](1.415<sup>''n''</sup>).<ref>{{Cite book |last=Bjorklund |first=Andreas |title=2010 IEEE 51st Annual Symposium on Foundations of Computer Science |chapter=Determinant Sums for Undirected Hamiltonicity |date=October 2010 |chapter-url=http://dx.doi.org/10.1109/focs.2010.24 |pages=173–182 |publisher=IEEE |doi=10.1109/focs.2010.24|arxiv=1008.0541 |isbn=978-1-4244-8525-3 }}</ref>