DocumentCode
655240
Title
The Parity of Directed Hamiltonian Cycles
Author
Bjorklund, Andreas ; Husfeldt, Thore
Author_Institution
Dept. of Comput. Sci., Lund Univ., Lund, Sweden
fYear
2013
fDate
26-29 Oct. 2013
Firstpage
727
Lastpage
735
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.619n) time and polynomial space. For bipartite graphs, we give a 1.5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
Keywords
computational complexity; deterministic algorithms; directed graphs; 1.5npoly(n) expected time algorithm; O(1.619n) time; bipartite graphs; deterministic algorithm; directed Hamiltonian cycles; directed graph; polynomial space; positive integer; Bipartite graph; Computer science; Educational institutions; Partitioning algorithms; Polynomials; Vectors;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location
Berkeley, CA
ISSN
0272-5428
Type
conf
DOI
10.1109/FOCS.2013.83
Filename
6686209
Link To Document