L773:0272 5428 OR L773:9781728196213 OR L773:9781728196220
Sökning: L773:0272 5428 OR L773:9781728196213 OR L773:9781728196220 > (2010-2014) > The Parity of Direc...
The Parity of Directed Hamiltonian Cycles
-
- Björklund, Andreas (författare)
- 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 (författare)
- 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
- Engelska 8 s.
- Ingår i: Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 727-735
- Konferensbidrag (refereegranskat)
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
- Annual IEEE Symposium on Foundations of Computer Science (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
Hitta mer i SwePub
- Av författaren/redakt...
- Björklund, Andre ...
- Husfeldt, Thore
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- och Datavetenskap
- Artiklar i publikationen
- Annual IEEE Symp ...
- Av lärosätet
- Lunds universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
