Computation of renameable Horn backdoors
作者： Stephan Kottler , Michael Kaufmann , Carsten Sinz
DOI: 10.1007/978-3-540-79719-7_15
关键词:
摘要: Satisfiability of real-world Sat instances can be often decided by focusing on a particular subset variables - so-called Backdoor Set. In this paper we suggest two algorithms to compute Renameable Horn deletion backdoors. Both methods are based the idea transform computation into graph problem. This approach could used as preprocessing solve hard instances. We also give some experimental results computations backdoors for several
springer.com
carstensinz.de参考文章(18)
Jianer Chen, Yang Liu, Songiian Lu, None, Directed Feedback Vertex Set Problem is FPT dagstuhl seminar proceedings. pp. 0- ,(2007)
Henry Kautz, Eric Horvitz, Yongshao Ruan, The backdoor key: a path to understanding problem hardness national conference on artificial intelligence. pp. 118- 123 ,(2004)
Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal, Tradeoffs in the complexity of backdoor detection principles and practice of constraint programming. pp. 256- 270 ,(2007) , 10.1007/978-3-540-74970-7_20
Stefan Szeider, Naomi Nishimura, Prabhakar Ragde, Detecting Backdoor Sets with Respect to Horn and Binary Clauses. theory and applications of satisfiability testing. pp. 96- 103 ,(2004)
Joshua Buresh-Oppenheim, David Mitchell, Minimum Witnesses for Unsatisfiable 2CNFs Lecture Notes in Computer Science. pp. 42- 47 ,(2006) , 10.1007/11814948_6
Bart Selman, Carla P. Gomes, Ryan Williams, Backdoors to typical case complexity international joint conference on artificial intelligence. pp. 1173- 1178 ,(2003)
Lionel Paris, Richard Ostrowski, Pierre Siegel, Lakhdar Sais, Computing Horn Strong Backdoor Sets Thanks to Local Search international conference on tools with artificial intelligence. pp. 139- 143 ,(2006) , 10.1109/ICTAI.2006.43
Camil Demetrescu, Irene Finocchi, Combinatorial algorithms for feedback problems in directed graphs Information Processing Letters. ,vol. 86, pp. 129- 136 ,(2003) , 10.1016/S0020-0190(02)00491-X
Harry R. Lewis, Renaming a Set of Clauses as a Horn Set Journal of the ACM. ,vol. 25, pp. 134- 135 ,(1978) , 10.1145/322047.322059