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: [img] PDF
Download (199kB) | Preview
Editorial actions: View Item View Item (Login required)
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:
  • 03-XX Mathematical logic and foundations > 03Bxx General logic > 03B05 Classical propositional logic

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 68-XX Computer science > 68Qxx Theory of computing > 68Q25 Analysis of algorithms and problem complexity

    		•
    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