Backbones and backdoors in satisfiability
Kilby, Philip; Slaney, John K; Thiebaux, Sylvie; Walsh, Toby
Description
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]
Collections | ANU Research Publications |
---|---|
Date published: | 2005 |
Type: | Conference paper |
URI: | http://hdl.handle.net/1885/83343 |
Source: | Proceedings of The Twentieth National Conference on Artificial Intelligence and The Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI-2005 / IAAI-2005) |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
01_Kilby_Backbones_and_backdoors_in_2005.pdf | 155.18 kB | Adobe 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