Picture of wind turbine against blue sky

Open Access research with a real impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs.

The Energy Systems Research Unit (ESRU) within Strathclyde's Department of Mechanical and Aerospace Engineering is producing Open Access research that can help society deploy and optimise renewable energy systems, such as wind turbine technology.

Explore wind turbine research in Strathprints

Explore all of Strathclyde's Open Access research content

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.

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.