Sökning: id:"swepub:oai:lup.lub.lu.se:eab0c0e5-0561-40ec-9269-eb93f444b820" >
Below All Subsets f...
Below All Subsets for Some Permutational Counting Problems
-
- 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
-
(creator_code:org_t)
- 2016
- 2016
- Engelska.
-
Ingår i: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). - 9783959770118 ; , s. 1-17
- Relaterad länk:
-
http://dx.doi.org/10... (free)
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.4...
-
visa färre...
Abstract
Ämnesord
Stäng
- We show that the two problems of computing the permanent of an n*n matrix of poly(n)-bit integers and counting the number of Hamiltonian cycles in a directed n-vertex multigraph with exp(poly(n)) edges can be reduced to relatively few smaller instances of themselves. In effect we derive the first deterministic algorithms for these two problems that run in o(2^n) time in the worst case. Classic poly(n)2^n time algorithms for the two problems have been known since the early 1960's. Our algorithms run in 2^{n-Omega(sqrt{n/log(n)})} time.
Ä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
Till lärosätets databas