Algorithms for Variable-Weighted 2-SAT and Dual Problems

DOI10.1007/978-3-540-72788-0_19zbMath1214.68368OpenAlexW1596197248MaRDI QIDQ3612465

Ewald Speckenmeyer, Stefan Porschen

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

optimization problemNP-hardnessperfect matchingedge coverweighted satisfiabilitygraph factor

Mathematics Subject Classification ID

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

Related Items (2)

Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ XSAT and NAE-SAT of linear CNF classes

Uses Software

• Ltur

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