Exact algorithms for exact satisfiability and number of perfect matchings
(2006) 33rd International Colloquium, ICALP 2006 4051. p.548559 Abstract
 We present exact algorithms with exponential running times for variants of nelement set cover problems, based on divideandconquer and on inclusionexclusion characterisations. We show that the Exact Satisfiability problem of size 1 with m clauses can be solved in time 2(m)l(O(1)) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an nvertex graph in time 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) and exponential space. Using the same techniques we show how to compute Chromatic Number of an nvertex graph in time O(2.4423(n)) and polynomial space, or time O(2.3236(n)) and... (More)
 We present exact algorithms with exponential running times for variants of nelement set cover problems, based on divideandconquer and on inclusionexclusion characterisations. We show that the Exact Satisfiability problem of size 1 with m clauses can be solved in time 2(m)l(O(1)) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an nvertex graph in time 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) and exponential space. Using the same techniques we show how to compute Chromatic Number of an nvertex graph in time O(2.4423(n)) and polynomial space, or time O(2.3236(n)) and exponential space. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/395335
 author
 Björklund, Andreas ^{LU} and Husfeldt, Thore ^{LU}
 organization
 publishing date
 2006
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Lecture Notes in Computer Science (Automata, Languages and Programming. Proceedings, Part I)
 volume
 4051
 pages
 548  559
 publisher
 Springer
 conference name
 33rd International Colloquium, ICALP 2006
 conference location
 Venice, Italy
 conference dates
 20060710  20060714
 external identifiers

 wos:000239474500048
 scopus:33746360269
 ISSN
 16113349
 03029743
 ISBN
 9783540359043
 DOI
 10.1007/11786986
 language
 English
 LU publication?
 yes
 id
 8f90055936dd4f20b1217ad75fa517f1 (old id 395335)
 date added to LUP
 20160401 12:37:51
 date last changed
 20210922 04:36:37
@inproceedings{8f90055936dd4f20b1217ad75fa517f1, abstract = {We present exact algorithms with exponential running times for variants of nelement set cover problems, based on divideandconquer and on inclusionexclusion characterisations. We show that the Exact Satisfiability problem of size 1 with m clauses can be solved in time 2(m)l(O(1)) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an nvertex graph in time 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) and exponential space. Using the same techniques we show how to compute Chromatic Number of an nvertex graph in time O(2.4423(n)) and polynomial space, or time O(2.3236(n)) and exponential space.}, author = {Björklund, Andreas and Husfeldt, Thore}, booktitle = {Lecture Notes in Computer Science (Automata, Languages and Programming. Proceedings, Part I)}, isbn = {9783540359043}, issn = {16113349}, language = {eng}, pages = {548559}, publisher = {Springer}, title = {Exact algorithms for exact satisfiability and number of perfect matchings}, url = {http://dx.doi.org/10.1007/11786986}, doi = {10.1007/11786986}, volume = {4051}, year = {2006}, }