A Linear Time Algorithm for Counting #2SAT on Series-Parallel Formulas

被引：1
|
作者：
Lopez-Medina, Marco A. [1 ]
Raymundo Marcial-Romero, J. [1 ]
De Ita-Luna, Guillermo [2 ]
Hernandez, Jose A. [1 ]
机构：
[1] UAEMex, Fac Ingn, Toluca, Mexico
[2] BUAP, Fac Ciencias Comp, Puebla, Mexico
来源：
ADVANCES IN SOFT COMPUTING, MICAI 2020, PT I | 2020年 / 12468卷
关键词：
#SAT; #2SAT; Complexity theory; Graph theory;
D O I：
10.1007/978-3-030-60884-2_33
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
An O(m + n) time algorithm is presented for counting the number of models of a two Conjunctive Normal Form Boolean Formula whose constrained graph is represented by a Series-Parallel graph, where n is the number of variables and m is the number of clauses. To the best of our knowledge, no linear time algorithm has been developed for counting in this kind of formulas.
引用
收藏
页码：437 / 447
页数：11
相关论文
共 50 条
12345