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. (http://dx.doi.org/10.1007/978-3-540-85958-1_53)

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.

• Share and Export
  

  RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomSimple MetadataReferMETSHTML CitationASCII CitationOpenURL ContextObjectEndNoteOpenURL ContextObject in SpanMODSMPEG-21 DIDLEP3 XMLData Cite XMLRIS (EndNote Online, Zotero, Ref manager, etc)RDF+N3Multiline CSV
• Item metadata

  Item type:	Conference or Workshop Item(Paper)
  ID code:	18118
  Dates:	Date Event 2008 Published
  Notes:	Also published in Lecture Notes in Computer Science, v. 5202, 2008, pp. 618-623
  Subjects:	Science > Mathematics > Electronic computers. Computer science
  Department:	Faculty of Science > Computer and Information Sciences
  Depositing user:	Strathprints Administrator
  Date deposited:	21 Apr 2010 19:08
  Last modified:	09 Apr 2024 05:22
  URI:	https://strathprints.strath.ac.uk/id/eprint/18118