# Boosting the Performance of CDCL-Based SAT Solvers by Exploiting Backbones and Backdoors
## 3 Related Work
### MapleLCMDistClronoBT-DL-v3 and LSTech
In Proceedings of the 12 th International Joint Conference on Artificial Intelligence--Volume 1, Sydney, Australia, 24-30 August 1991; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 1991; IJCAI'91; pp. 331-337. * [PERSON] et al. (1999) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Determining computational complexity from characteristic 'phase transitions'. _Nature_**1999**, _400_, 133-137. [CrossRef]
* [PERSON] et al. (2003) [PERSON]; [PERSON]; [PERSON] Backdoors to Typical Case Complexity. In Proceedings of the 18 th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 9-15 August 2003; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 2003; IJCAI'03; pp. 1173-1178. * [PERSON] et al. (2018) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Learning-Sensitive Backdoors with Restarts. In Proceedings of the Principles and Practice of Constraint Programming 2018, Lille, France, 27-31 August 2018; Volume 11008, pp. 453-469. * [PERSON] et al. (2005) [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON] Backbones and Backdoors in Satisfiability. In Proceedings of the 20 th National Conference on Artificial Intelligence, Pittsburgh, PA, USA, 9-13 July 2005; AAAI'05; pp. 1368-1373. * [PERSON] and [PERSON] (2008) [PERSON]; [PERSON]; [PERSON] A New Empirical Study of Weak Backdoors. In Proceedings of the Principles and Practice of Constraint Programming, Sydney, Australia, 14-18 September 2008; [PERSON]: Berlin/Heidelberg, Germany, 2008; pp. 618-623. * [PERSON] et al. (2006) [PERSON]; [PERSON]; [PERSON]; [PERSON] Computing Horn Strong Backdoor Sets Thanks to Local Search. In Proceedings of the 2006 18 th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06), Arlington, VA, USA, 13-15 November 2006; pp. 139-143. [CrossRef]
* [PERSON] et al. (2005) [PERSON]; [PERSON]; [PERSON] The Backbone of the Travelling Salesperson. In Proceedings of the 19 th International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, 30 July-5 August 2005; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 2005; IJCAI'05; p. 175-180. * [PERSON] and [PERSON] (2003) [PERSON]; [PERSON] [PERSON] kcnfs: An Efficient Solver for Random k-SAT Formulae. In Proceedings of the Theory and Applications of Satisfiability Testing, 6 th International Conference, Santa Margherita Ligure, Italy, 5-8 May 2003; Volume 2919, pp.486-501. [CrossRef]
* [PERSON] et al. (2022) [PERSON]; [PERSON]; [PERSON] On the Structure of the Boolean Satisfiability Problem: A Survey. _ACM Comput. Surv._**2022**, _55_, 1-34. * [PERSON] et al. (2015) [PERSON]; [PERSON]; [PERSON] Algorithms for computing backbones of propositional formulae. _AI Commun._**2015**, _28_, 161-177. [CrossRef]
* [PERSON] et al. (2009) [PERSON]; [PERSON]; [PERSON] Backdoors in the Context of Learning. In Proceedings of the Theory and Applications of Satisfiability Testing 2009, Swansea, Wales, UK, 30 June-3 July 2009; Volume 5584, pp. 73-79. * [PERSON] and [PERSON] (1960) [PERSON]; [PERSON] [PERSON] A Computing Procedure for Quantification Theory. _J. ACM_**1960**, \(7\), 201-215. [CrossRef]
* [PERSON] and [PERSON] (1999) [PERSON]; [PERSON] GRASP: A search algorithm for propositional satisfiability. _IEEE Trans. Comput._**1999**, _48_, 506-521. [CrossRef]
* [PERSON] and [PERSON] (2007) [PERSON]; [PERSON] [PERSON] BerkMin: A fast and robust Sat-solver. _Discret. Appl. Math._**2007**, _155_, 1549-1561. [CrossRef]
* [PERSON] et al. (1998) [PERSON]; [PERSON]; [PERSON] Boosting Combinatorial Search Through Randomization. In Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, Madison, WI, USA, 26-30 July 1998; pp. 431-437. * [PERSON] and [PERSON] (2003) [PERSON]; [PERSON] An Extensible SAT-solver. In Proceedings of the Theory and Applications of Satisfiability Testing 2003, Santa Margherita Ligure, Italy, 5-8 May 2003; Volume 2919, pp. 502-518. * [PERSON] et al.