Name
Abstract | ||
|---|---|---|
Although the satisfiability problem for two Conjunctive Normal Form formulas (2SAT) is polynomial time solvable, it is well known that #2SAT, the counting version of 2SAT is # P-Complete. However, it has been shown that for certain classes of formulas, #2SAT can be computed in polynomial time. In this paper we show another class of formulas for which #2SAT can also be computed in lineal time, the so called outerplanar formulas, e. g. formulas whose signed primal graph is outerplanar. Our algorithm's time complexity is given by O(n+ m) where n is the number of variables and m the number of clauses of the formula. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-92198-3_8 | PATTERN RECOGNITION |
Field | DocType | Volume |
Graph,Computer science,Boolean satisfiability problem,Algorithm,Conjunctive normal form,Time complexity | Conference | 10880 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marco A. López | 1 | 171 | 21.03 |
| José Raymundo Marcial-Romero | 2 | 5 | 12.87 |
| Guillermo De Ita Luna | 3 | 29 | 16.57 |
| Yolanda Moyao | 4 | 1 | 2.32 |