Complete Boolean satisfiability solving algorithms based on local search

DOI10.1007/s11390-013-1326-4zbMath1280.68241MaRDI 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

set; local search; clique; Boolean satisfiability; complete search

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

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