Nested and co-nested formulas are two classes of CNF instances that can be characterized in terms of outerplanar graphs. For these classes, linear time algorithms are known for SAT and (unweighted) Max-SAT. In this paper we devise linear time algorithms for a general optimization version of SAT. Moreover, we show that a general probabilistic version of SAT reduces to solving a system of linear inequalities where the number of variables and constraints is linear in the size of the formula.
Optimization and probabilistic satisfiability on nested and co-nested formulas / Pretolani, Daniele. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 188:1(2011), pp. 371-387. [10.1007/s10479-008-0502-3]
Optimization and probabilistic satisfiability on nested and co-nested formulas
PRETOLANI, Daniele
2011
Abstract
Nested and co-nested formulas are two classes of CNF instances that can be characterized in terms of outerplanar graphs. For these classes, linear time algorithms are known for SAT and (unweighted) Max-SAT. In this paper we devise linear time algorithms for a general optimization version of SAT. Moreover, we show that a general probabilistic version of SAT reduces to solving a system of linear inequalities where the number of variables and constraints is linear in the size of the formula.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
