Algorithms for Variable-Weighted 2-SAT and Dual Problems

Porschen, Stefan and Speckenmeyer, Ewald (2007) Algorithms for Variable-Weighted 2-SAT and Dual Problems.
Technical Report , 14 p.


In this paper we study NP-hard weighted satisfiability optimization problems for the class 2-CNF providing worst-case upper time bounds. Moreover we consider the monotone dual class consisting of clause sets where all variables occur at most twice. We show that weighted SAT, XSAT and NAESAT optimization problems for this class are polynomial time solvable using appropriate reductions to specific polynomial time solvable graph problems.

Download: [img] PDF
Download (199kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-534
Depositing User: Stefan Porschen
Date Deposited: 01 Feb 2007 00:00
Last Modified: 19 Dec 2011 09:44