Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

The Parity of Directed Hamiltonian Cycles

Björklund, Andreas LU and Husfeldt, Thore LU (2013) 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) p.727-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.
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Annual IEEE Symposium on Foundations of Computer Science
pages
8 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
conference location
Berkeley, CA, United States
conference dates
2013-10-26 - 2013-10-29
external identifiers
  • scopus:84893432664
  • wos:000330672400075
ISSN
0272-5428
DOI
10.1109/FOCS.2013.83
project
Exact algorithms
language
English
LU publication?
yes
id
56c84795-ff92-4cdf-afaa-05c66155f722 (old id 4247263)
date added to LUP
2016-04-01 14:20:55
date last changed
2022-01-28 00:07:39
@inproceedings{56c84795-ff92-4cdf-afaa-05c66155f722,
  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.}},
  author       = {{Björklund, Andreas and Husfeldt, Thore}},
  booktitle    = {{Annual IEEE Symposium on Foundations of Computer Science}},
  issn         = {{0272-5428}},
  language     = {{eng}},
  pages        = {{727--735}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{The Parity of Directed Hamiltonian Cycles}},
  url          = {{http://dx.doi.org/10.1109/FOCS.2013.83}},
  doi          = {{10.1109/FOCS.2013.83}},
  year         = {{2013}},
}