Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Exact algorithms for exact satisfiability and number of perfect matchings

In English

Författare

Summary, in 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.

Publiceringsår

2008

Språk

Engelska

Sidor

226-249

Publikation/Tidskrift/Serie

Algorithmica

Volym

52

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • exact algorithms
  • set partition
  • exact satisfability
  • number
  • of perfect matchings
  • set cover

Status

Published

Projekt

  • Exact algorithms

Forskningsgrupp

  • Algorithms

ISBN/ISSN/Övrigt

  • ISSN: 0178-4617