Du är här

Exact algorithms for exact satisfiability and number of perfect matchings

Publiceringsår: 2008
Språk: Engelska
Sidor: 226-249
Publikation/Tidskrift/Serie: Algoritmica
Volym: 52
Nummer: 2
Dokumenttyp: Artikel
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 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.

Disputation

Nyckelord

  • Technology and Engineering
  • exact algorithms
  • set partition
  • exact satisfability
  • number
  • of perfect matchings
  • set cover

Övriga

  • VR
Published
  • Exact algorithms
Yes
  • Algorithms
  • ISSN: 0178-4617

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