Abstract | ||
---|---|---|
We present a novel algorithm based on combinatorial operations on lists for computing the number of models on two conjunctive normal form Boolean formulas whose restricted graph is represented by a grid graph G(m, n). We show that our algorithm is correct and its time complexity is O(root t . 1.618(root t+2) + t . 1.6182(root t+4)), where t = n . m is the total number of vertices in the graph. For this class of formulas, we show that our proposal improves the asymptotic behavior of the time-complexity with respect of the current leader algorithm for counting models on two conjunctive form formulas of this kind. |
Year | DOI | Venue |
---|---|---|
2022 | 10.3233/JIFS-219259 | JOURNAL OF INTELLIGENT & FUZZY SYSTEMS |
Keywords | DocType | Volume |
#SAT, #2SAT, models of boolean formulas, combinatorial algorithms, complexity theory | Journal | 42 |
Issue | ISSN | Citations |
5 | 1064-1246 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marco A. Lopez-Medina | 1 | 0 | 0.34 |
J. Raymundo Marcial-Romero | 2 | 0 | 0.34 |
Guillermo De Ita Luna | 3 | 29 | 16.57 |
Jose A. Hernandez | 4 | 0 | 0.34 |