TY - JOUR
T1 - Recognition of q-Horn formulae in linear time
AU - Boros, Endre
AU - Hammer, Peter L.
AU - Sun, Xiaorong
N1 - Funding Information:
+This research was supported in part by NSF (Grant DMS 89-06870) 90-0008) and ONR (Grants NOOOl4-92-51375 and N00014-92-54083).
PY - 1994/10/28
Y1 - 1994/10/28
N2 - The class of q-Horn Boolean expressions, generalizing the important classes of quadratic, Horn, and disguised Horn formulae, has been introduced in Boros et al.(1990). It has been shown there that the satisfiability problem corresponding to a disjunctive normal form φ is solvable in time, linear in the size of φ, if φ is known to be q-Horn. However, the recognition of such formulae was based on the solution of a linear programming problem, and had therefore a much higher (although still polynomial) complexity. In this paper a linear-time combinatorial algorithm is presented for recognizing q-Horn formulae, and reducing in this way the overall complexity of the corresponding satisfiability problem to a linear one.
AB - The class of q-Horn Boolean expressions, generalizing the important classes of quadratic, Horn, and disguised Horn formulae, has been introduced in Boros et al.(1990). It has been shown there that the satisfiability problem corresponding to a disjunctive normal form φ is solvable in time, linear in the size of φ, if φ is known to be q-Horn. However, the recognition of such formulae was based on the solution of a linear programming problem, and had therefore a much higher (although still polynomial) complexity. In this paper a linear-time combinatorial algorithm is presented for recognizing q-Horn formulae, and reducing in this way the overall complexity of the corresponding satisfiability problem to a linear one.
UR - http://www.scopus.com/inward/record.url?scp=0002216450&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0002216450&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(94)90033-7
DO - 10.1016/0166-218X(94)90033-7
M3 - Article
AN - SCOPUS:0002216450
SN - 0166-218X
VL - 55
SP - 1
EP - 13
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1
ER -