A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth
| dc.creator | Samer, Marko | |
| dc.creator | Szeider, Stefan | |
| dc.date | 2006-10-31 | |
| dc.date | 2007-02-21 | |
| dc.date.accessioned | 2026-07-07T07:47:44Z | |
| dc.date.available | 2026-07-07T07:47:44Z | |
| dc.description | We present an efficient fixed-parameter algorithm for #SAT parameterized by the incidence treewidth, i.e., the treewidth of the bipartite graph whose vertices are the variables and clauses of the given CNF formula; a variable and a clause are joined by an edge if and only if the variable occurs in the clause. Our algorithm runs in time O(4^k k l N), where k denotes the incidence treewidth, l denotes the size of a largest clause, and N denotes the number of nodes of the tree-decomposition. | |
| dc.description | 9 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/cs/0610174 | |
| dc.identifier | http://arxiv.org/abs/cs/0610174 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/124269 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.2.2; F.4.1 | |
| dc.title | A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth | |
| dc.type | text |