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.
Abstract
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.
Actions:
Download: |
Download (199kB) | Preview |
---|---|
Editorial actions: | ![]() |
Content information:
Item Type: | Paper (Technical Report) |
---|---|
Citations: | 1 (Google Scholar) | 1 (Web of Science) |
Uncontrolled Keywords: | weighted satisfiability optimization problem NP-hardness edge cover graph factor perfect matching |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Speckenmeyer |
Related URLs: |
Deposit Information:
ZAIK Number: | zaik2007-534 |
---|---|
Depositing User: | Stefan Porschen |
Date Deposited: | 01 Feb 2007 00:00 |
Last Modified: | 19 Dec 2011 09:44 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/534 |