A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas

doi:10.1007/978-3-319-92198-3_8

A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas

2018-05-25

4

PRE

AI

J

J. Raymundo Marcial‐Romero *

G

Guillermo De Ita Luna

DOI：10.1007/978-3-319-92198-3_8

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

MERRIFIELD-SIMMONS INDEX

HOSOYA INDEX

A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas

Abstract

Journal

Organization