The Parity of Directed Hamiltonian Cycles

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationAnnual IEEE Symposium on Foundations of Computer Science
FörlagIEEE--Institute of Electrical and Electronics Engineers Inc.
Sidor727-735
Antal sidor8
StatusPublished - 2013
PublikationskategoriForskning
Peer review utfördJa
Evenemang54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) - Berkeley, CA, USA
Varaktighet: 2013 okt 262013 okt 29

Publikationsserier

Namn
ISSN (tryckt)0272-5428

Konferens

Konferens54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
LandUSA
OrtBerkeley, CA
Period2013/10/262013/10/29