Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Exact algorithms for exact satisfiability and number of perfect matchings

Björklund, Andreas LU and Husfeldt, Thore LU (2006) 33rd International Colloquium, ICALP 2006 4051. p.548-559
Abstract
We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion-exclusion 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 n-vertex 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 n-vertex 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 n-element set cover problems, based on divide-and-conquer and on inclusion-exclusion 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 n-vertex 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 n-vertex 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:
author
and
organization
publishing date
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
2006-07-10 - 2006-07-14
external identifiers
  • wos:000239474500048
  • scopus:33746360269
ISSN
1611-3349
0302-9743
ISBN
978-3-540-35904-3
DOI
10.1007/11786986
language
English
LU publication?
yes
id
8f900559-36dd-4f20-b121-7ad75fa517f1 (old id 395335)
date added to LUP
2016-04-01 12:37:51
date last changed
2021-09-22 04:36:37
@inproceedings{8f900559-36dd-4f20-b121-7ad75fa517f1,
  abstract     = {We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion-exclusion 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 n-vertex 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 n-vertex 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         = {978-3-540-35904-3},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {548--559},
  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},
}