Search: (L773:0272 5428 OR L773:9781728196213 OR L773:9781728196220) srt2:(2010-2014)
> (2013) >
The Parity of Direc...
The Parity of Directed Hamiltonian Cycles
-
- Björklund, Andreas (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
(creator_code:org_t)
- 2013
- 2013
- English 8 s.
-
In: Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 727-735
- Related links:
-
http://dx.doi.org/10...
-
show more...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
To the university's database