The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

The Parity of Directed Hamiltonian Cycles

På svenska

Author

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.

Publishing year

2013

Language

English

Pages

727-735

Publication/Series

Annual IEEE Symposium on Foundations of Computer Science

Document type

Conference paper

Publisher

IEEE - Institute of Electrical and Electronics Engineers Inc.

Topic

  • 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

Project

  • Exact algorithms

Research group

  • Algorithms

ISBN/ISSN/Other

  • ISSN: 0272-5428