Complete Boolean satisfiability solving algorithms based on local search

DOI10.1007/s11390-013-1326-4zbMath1280.68241OpenAlexW2094668451MaRDI QIDQ2434568

Xiaoyu Song, William N. N. Hung, Wensheng Guo, Guo-wu Yang

Publication date: 6 February 2014

Published in: Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11390-013-1326-4

zbMATH Keywords

setlocal searchcliqueBoolean satisfiabilitycomplete search

Mathematics Subject Classification ID

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

Uses Software

• zChaff
• SATzilla
• RSat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Adaptive channel and power allocation of downlink multi-user MC-CDMA systems
• Cross-layer packet scheduling for downlink multiuser OFDM systems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Many hard examples in exact phase transitions
• Two Hardness Results on Feedback Vertex Sets
• Solving SAT and SAT Modulo Theories
• A Note on Treewidth in Random Graphs
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Complete Boolean satisfiability solving algorithms based on local search