Exact algorithms for exact satisfiability and number of perfect matchings

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationLecture Notes in Computer Science (Automata, Languages and Programming. Proceedings, Part I)
FörlagSpringer
Sidor548-559
Volym4051
ISBN (tryckt)978-3-540-35904-3
StatusPublished - 2006
PublikationskategoriForskning
Peer review utfördJa
Evenemang33rd International Colloquium, ICALP 2006 - Venice, Italien
Varaktighet: 2006 jul 102006 jul 14

Publikationsserier

Namn
Volym4051
ISSN (tryckt)1611-3349
ISSN (elektroniskt)0302-9743

Konferens

Konferens33rd International Colloquium, ICALP 2006
LandItalien
OrtVenice
Period2006/07/102006/07/14