The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Exact algorithms for exact satisfiability and number of perfect matchings

På svenska

Author

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

Publishing year

2006

Language

English

Pages

548-559

Publication/Series

Lecture Notes in Computer Science (Automata, Languages and Programming. Proceedings, Part I)

Volume

4051

Document type

Conference paper

Publisher

Springer

Topic

  • 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/Other

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