40 citations · 61 across the 13 of their papers we have counts for
5 papers · 1 filter
Phase Transitions in Knowledge Compilation: an Experimental Study
Jian Gao, Minghao Yin, Ke Xu
Phase transitions in many complex combinational problems have been widely studied in the past decade. In this paper, we investigate phase transitions in the knowledge compilation e…
New Worst-Case Upper Bound for X3SAT
Junping Zhou, Minghao Yin
The rigorous theoretical analyses of algorithms for exact 3-satisfiability (X3SAT) have been proposed in the literature. As we know, previous algorithms for solving X3SAT have been…
Worst-Case Upper Bound for (1, 2)-QSAT
Minghao Yin
The rigorous theoretical analysis of the algorithm for a subclass of QSAT, i.e. (1, 2)-QSAT, has been proposed in the literature. (1, 2)-QSAT, first introduced in SAT'08, can be se…
New Worst-Case Upper Bound for #XSAT
Junping Zhou, Minghao Yin
An algorithm running in O(1.1995n) is presented for counting models for exact satisfiability formulae(#XSAT). This is faster than the previously best algorithm which runs in O(1.21…
Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm
Minghao Yin, Ping Huang
The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of researc…