Skip navigation
Skip navigation

Backbones and backdoors in satisfiability

Kilby, Philip; Slaney, John K; Thiebaux, Sylvie; Walsh, Toby


We study the backbone and the backdoors of prepositional satisfiability problems. We make a number of theoretical, algorithmic and experimental contributions. From a theoretical perspective, we prove that backbones are hard even to approximate. From an algorithmic perspective, we present a number of different procedures for computing backdoors. From an empirical perspective, we study the correlation between being in the backbone and in a backdoor. Experiments show that there tends to be very...[Show more]

CollectionsANU Research Publications
Date published: 2005
Type: Conference paper
Source: Proceedings of The Twentieth National Conference on Artificial Intelligence and The Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI-2005 / IAAI-2005)


File Description SizeFormat Image
01_Kilby_Backbones_and_backdoors_in_2005.pdf155.18 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator