Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)

被引：0

作者：

Ordyniak, Sebastian ^{[1
]}

Paulusma, Daniel ^{[2
]}

Szeider, Stefan ^{[1
]}

机构：

[1] Vienna Univ Technol, Inst Informat Syst, A-1040 Vienna, Austria

[2] Univ Durham, Sch Engn & Comp Sci, Durham DH1 3LE, England

来源：

THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2011 | 2011年 / 6695卷

基金：

英国工程与自然科学研究理事会;

关键词：

CLIQUE-WIDTH; HYPERGRAPHS; ALGORITHMS; GRAPHS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the first part of this work (FSTTCS' 10) we have shown that the satisfiability of CNF formulas with beta-acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for beta-acyclic formulas is based on a special type of Davis-Putnam resolution where each resolvent is a subset of a parent clause. We generalize the class of beta-acyclic formulas to more general CNF formulas for which this type of Davis-Putnam resolution still applies. We then compare the class of beta-acyclic formulas and this superclass with a number of known polynomial formula classes.

引用

页码：47 / 60

页数：14

共 17 条

[1] A partial k-arboretum of graphs with bounded treewidth
Bodlaender, HL
[J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
[2] Brandstädt A, 2003, ARS COMBINATORIA, V67, P273
[3] Brandstadt A., 1999, SIAM MONOG DISCR MAT
[4] Upper bounds to the clique width of graphs
Courcelle, B
Olariu, S
[J]. DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) : 77 - 114
[5] A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY
DAVIS, M
PUTNAM, H
[J]. JOURNAL OF THE ACM, 1960, 7 (03) : 201 - 215
[6] DEGREES OF ACYCLICITY FOR HYPERGRAPHS AND RELATIONAL DATABASE SCHEMES
FAGIN, R
[J]. JOURNAL OF THE ACM, 1983, 30 (03) : 514 - 550
[7] Counting truth assignments of formulas of bounded tree-width or clique-width
Fischer, E.
Makowsky, J. A.
Ravve, Ex
[J]. DISCRETE APPLIED MATHEMATICS, 2008, 156 (04) : 511 - 529
[8] Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
[J]. IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2010), 2010, 8 : 73 - 83
[9] Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems
Gottlob, Georg
Szeider, Stefan
[J]. COMPUTER JOURNAL, 2008, 51 (03) : 303 - 325
[10] KLOKS T, 1992, LECT NOTES COMPUT SC, V650, P116

← 1 2 →