Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

A new empirical study of weak backdoors

Gregory, P. and Fox, M. and Long, D. (2008) A new empirical study of weak backdoors. In: 14th International Conference on Principles and Practice of Constraint Programming, 2008-09-01, Sydney, Australia.

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

Work by Kilby, Slaney, Thiebaux and Walsh [1] showed that the backdoors and backbones of unstructured Random 3SAT instances are largely disjoint. In this work we extend this study to the consideration of backdoors in SAT encodings of structured problems. We show that the results of Kilby et al. also apply to structured problems. Further, we analyse the frequency with which individual variables appear in backdoors for specific problem instances. In all problem classes there are variables with particularly high frequencies of backdoor membership. Backbone variables that do appear in backdoors typically appear in very few.

Item type: Conference or Workshop Item (Paper)
ID code: 18118
Notes: Also published in Lecture Notes in Computer Science, v. 5202, 2008, pp. 618-623
Keywords: weak backdoors, SAT encodings, structured problems, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
    Depositing user: Strathprints Administrator
    Date Deposited: 21 Apr 2010 20:08
    Last modified: 17 Jul 2013 15:48
    URI: http://strathprints.strath.ac.uk/id/eprint/18118

    Actions (login required)

    View Item