Algorithms for Variable-Weighted 2-SAT and Dual Problems

DOI10.1007/978-3-540-72788-0_19zbMATH Open1214.68368OpenAlexW1596197248MaRDI QIDQ3612465FDOQ3612465

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

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

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)

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
• Title not available (Why is that?)

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)