Du är här

Exact algorithms for exact satisfiability and number of perfect matchings

Publiceringsår: 2006
Språk: Engelska
Sidor: 548-559
Publikation/Tidskrift/Serie: Lecture Notes in Computer Science (Automata, Languages and Programming. Proceedings, Part I)
Volym: 4051
Dokumenttyp: Konferensbidrag
Förlag: Springer

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering

Övrigt

33rd International Colloquium, ICALP 2006
2014-07-11
Venice, Italy
Published
Yes
  • ISSN: 0302-9743
  • ISBN: 978-3-540-35904-3

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen

LERU logo U21 logo