Algorithms for Variable-Weighted 2-SAT and Dual Problems

DOI10.1007/978-3-540-72788-0_19MaRDI QIDQ3612465zbMATH OpenOpenAlexFDO

Authors Stefan Porschen, Ewald Speckenmeyer

Publication date 10 March 2009

Published in Theory and Applications of Satisfiability Testing – SAT 2007 (Search for Journal in Brave)

Full work available at URL http://e-archive.informatik.uni-koeln.de/534/2/zaik2007-534.pdf

zbMATH Keywords

edge covergraph factorNP-hardnessoptimization problemperfect matchingweighted satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On variable-weighted exact satisfiability problems
• SOFSEM 2005: Theory and Practice of Computer Science
• Algorithms and Computation
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications

Cited in

(6)

• XSAT and NAE-SAT of linear CNF classes
• On variable-weighted exact satisfiability problems
• scientific article; zbMATH DE number 1775484 (Why is no real title available?)
• SOFSEM 2005: Theory and Practice of Computer Science
• Algorithms and Computation
• Parameterized and subexponential-time complexity of satisfiability problems and applications

Describes a project that uses

Uses Software

• Ltur

This page was built for publication: Algorithms for Variable-Weighted 2-SAT and Dual Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3612465)