Journal article
Backdoors into heterogeneous classes of SAT and CSP
- Abstract:
-
In this paper we extend the classical notion of strong and weak backdoor sets for SAT and CSP by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for ...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Australian Government
More from this funder
+ Employment of Newly Graduated Doctors of Science for Scientific Excellence
More from this funder
Grant:
CZ.1.07/2.3.00/30.0009
Expand funders...
Bibliographic Details
- Publisher:
- Elsevier Publisher's website
- Journal:
- Journal of Computer and System Sciences Journal website
- Volume:
- 85
- Pages:
- 38-56
- Publication date:
- 2016-11-01
- Acceptance date:
- 2016-10-23
- DOI:
- ISSN:
-
0022-0000 and 1090-2724
- Source identifiers:
-
654370
Item Description
- Keywords:
- Pubs id:
-
pubs:654370
- UUID:
-
uuid:88836faf-6750-41d2-8f9c-ba7c96a410c5
- Local pid:
- pubs:654370
- Deposit date:
- 2017-03-02
Terms of use
- Copyright holder:
- Živný et al
- Copyright date:
- 2016
- Notes:
- © 2016 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record