Algorithms Seminar: Thore Husfeldt (Lund)
Date: June 08, 2006 (Thursday) at 14:15 to 15:00
Exact algorithms for exact satisfiabiilty and number of perfect matchings
Joint work with Andreas Björklund (Lund)
To appear at ICALP 2006
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 l with m clauses can be solved in time $2^ml^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.732n) and exponential space.
Using the same techniques we show how to compute Chromatic Number of an n-vertex graph in time O(2.4423n) and polynomial space, or time O(2.3236n ) and exponential space.
Room: E:2405
Last modified Dec 9, 2011 12:59 pm
0631