Below All Subsets for Some Permutational Counting Problems
(2016) 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) p.117 Abstract
 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 nvertex 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^{nOmega(sqrt{n/log(n)})} time.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/eab0c0e5056140ec9269eb93f444b820
 author
 Björklund, Andreas ^{LU}
 organization
 publishing date
 2016
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
 pages
 1  17
 conference name
 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
 external identifiers

 scopus:85011949857
 DOI
 10.4230/LIPIcs.SWAT.2016.17
 language
 English
 LU publication?
 yes
 id
 eab0c0e5056140ec9269eb93f444b820
 date added to LUP
 20160728 12:51:15
 date last changed
 20170226 04:40:12
@inproceedings{eab0c0e5056140ec9269eb93f444b820, abstract = {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 nvertex 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^{nOmega(sqrt{n/log(n)})} time. }, author = {Björklund, Andreas}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, language = {eng}, pages = {117}, title = {Below All Subsets for Some Permutational Counting Problems}, url = {http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.17}, year = {2016}, }