id:"swepub:oai:lup.lub.lu.se:c9b512bf-d79f-40b5-b1e9-ce1ad5ab422e"
Search: id:"swepub:oai:lup.lub.lu.se:c9b512bf-d79f-40b5-b1e9-ce1ad5ab422e" > Exact algorithms fo...
- 1 of 1
- Previous record
- Next record
- To hitlist
Exact algorithms for exact satisfiability and number of perfect matchings
-
- Björklund, Andreas (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (author)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
- (creator_code:org_t)
- 2007-12-14
- 2008
- English.
- In: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 52:2, s. 226-249
- Journal article (peer-reviewed)
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- exact algorithms
- set partition
- exact satisfability
- number
- of perfect matchings
- set cover
Publication and Content Type
- art (subject category)
- ref (subject category)
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Björklund, Andre ...
- Husfeldt, Thore
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Algorithmica
- By the university
- Lund University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
