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 coverNP-hardnessperfect matchingoptimization problemweighted satisfiabilitygraph factor

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) 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)

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

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)