Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction

DOI10.1007/978-3-319-09284-3_4zbMath1423.68471OpenAlexW1567941403MaRDI QIDQ3192053

Takayuki Sakai, Suguru Tamaki, Kazuhisa Seto

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-09284-3_4

zbMATH Keywords

countingweightpolynomial spaceexponential time algorithmhard constraint

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (1)

Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP

This page was built for publication: Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction