The Parity of Directed Hamiltonian Cycles

Summary, in English

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.

• Författare: Andreas Björklund; Thore Husfeldt
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2013
• Språk: Engelska
• Sidor: 727-735
• Publikation/Tidskrift/Serie: Annual IEEE Symposium on Foundations of Computer Science
• Länkar: http://dx.doi.org/10.1109/FOCS.2013.83
• Dokumenttyp: Konferensbidrag
• Förlag: IEEE - Institute of Electrical and Electronics Engineers Inc.
• Ämne: Computer Science
• Conference name: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
• Conference date: 2013-10-26 - 2013-10-29
• Conference place: Berkeley, CA, United States
• Status: Published
• Projekt: Exact algorithms
• Forskningsgrupp: Algorithms
• ISBN/ISSN/Övrigt: ISSN: 0272-5428