Name
Abstract | ||
|---|---|---|
An O(n+m)-time algorithm is presented for counting the number of models of a two Conjunctive Normal Form Formula F that represents a Cactus graph, where n is the number of variables and m is the number of clauses of F. Although, it was already known that this class of formulas could be computed in polynomial time, we compare our proposal algorithm with two state of the art implementations for the same problem, sharpSAT and countAntom. The results of the comparison show that our algorithm outperforms both implementations, and it can be considered as a base case for general counting of two Conjunctive Normal Form Formulas. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Logic in Computer Science | Discrete mathematics,Combinatorics,Algorithm,Cactus,Conjunctive normal form,Time complexity,Mathematics,Cactus graph |
DocType | Volume | Citations |
Journal | abs/1702.08581 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. A. López | 1 | 37 | 4.48 |
| José Raymundo Marcial-Romero | 2 | 5 | 12.87 |
| Guillermo De Ita Luna | 3 | 29 | 16.57 |
| Héctor A. Montes Venegas | 4 | 0 | 0.34 |
| Roberto Alejo | 5 | 0 | 1.69 |