@inproceedings{b46c487efa554823aabf94e3ee3433a8,
title = "Algorithmic analysis on a class of Boolean equations",
abstract = "Efficient procedures for satisfiability verification are foundations of numerical simulation and algorithmic analysis of NP-complete problems. Previous researches in this direction include well-known Davis-Putnam-Logemann-Loveland (DPLL) and leaf removal procedures. In this paper, we propose a new procedure called Leaf-removal Gaussian Elimination procedure (LGC) to verify the satisfiability of a class of NP-complete problems. This novel procedure is much simpler and faster than the original DPLL procedure. We also provide estimation of the phase transition point based on this procedure. Numerical experiments are conducted for Boolean equations systems with different parameters and the results verify the validity and efficiency of our novel techniques.",
author = "Wei Wei and Binghui Guo and Hongbo Zhou and Zhiming Zheng",
year = "2010",
month = dec,
day = "6",
doi = "10.1109/ICCASM.2010.5622117",
language = "English",
isbn = "9781424472369",
series = "ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings",
pages = "V12170--V12173",
booktitle = "ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings",
note = "null ; Conference date: 22-10-2010 Through 24-10-2010",
}