Your most visited
- Sorry, this tool will only work with Javascript available.
| Title | Exact algorithms for exact satisfiability and number of perfect matchings |
| Author/s | Andreas Björklund, Thore Husfeldt |
| Department/s |
Department of Computer Science
|
| Full-text | Full text is not available in this archive |
| Alternative location (URL) | http://dx.doi.org/10.1007/s004... Restricted Access (Alternative Location) |
| Publication/Series | Algoritmica |
| Publishing year | 2008 |
| Volume | 52 |
| Issue | 2 |
| Pages | 226 - 249 |
| Document type | Journal article |
| Status | published |
| Quality controlled | yes |
| Language | English |
| Publisher | Springer |
| Abstract English | 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 characterizations. We show that the Exact Satisfiability problem of size l 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. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number. |
| Subject |
Technology and Engineering |
| Keywords | set partition, exact algorithms, exact satisfability, number, of perfect matchings, set cover |
| ISBN/ISSN/Other |
ISSN: 0178-4617 |
| Research group | Algorithms |
| Project | Exact algorithms |
| Funder |
VR |
