Porschen, Stefan and Speckenmeyer, Ewald (2007). Algorithms for Variable-Weighted 2-SAT and Dual Problems. Working Paper.

[thumbnail of zaik2007-534.pdf]
Preview
 PDF
zaik2007-534.pdf
Download (199kB) | Preview

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.

Item Type: Monograph (Working Paper)
Creators:
Creators
Email
ORCID
ORCID Put Code
Porschen, Stefan
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Speckenmeyer, Ewald
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
URN: urn:nbn:de:hbz:38-549086
Date: 2007
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54908

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item