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

  • Andreas Björklund
  • Thore Husfeldt

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 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.

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

Ämne

  • Computer Science

Conference name

33rd International Colloquium, ICALP 2006

Conference date

2006-07-10 - 2006-07-14

Conference place

Venice, Italy

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-35904-3