Backdoors into heterogeneous classes of SAT and CSPReportar como inadecuado




Backdoors into heterogeneous classes of SAT and CSP - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Gaspers, S, Misra, N, Ordyniak, S et al., (2016). Backdoors into heterogeneous classes of SAT and CSP. Journal of Computer and System Sciences, 85, 38-56.Citable link to this page:

 

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 the problem of detecting strong and weak backdoor sets into heterogeneous base classes for SAT and CSP.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's versionDate of acceptance:2016-10-23 Funder: Australian Research Council   Funder: Australian Government   Funder: Indian Department of Science and Technology   Funder: Employment of Newly Graduated Doctors of Science for Scientific Excellence   Funder: European Research Council   Funder: Austrian Science Funds   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/).

Bibliographic Details

Publisher: Elsevier

Publisher Website: http://www.sciencedirect.com/

Journal: Journal of Computer and System Sciencessee more from them

Publication Website: http://www.sciencedirect.com/science/journal/00220000

Volume: 85

Extent: 38-56

Issue Date: 2016-11

pages:38-56Identifiers

Doi: https://doi.org/10.1016/j.jcss.2016.10.007

Issn: 1090-2724

Issn: 0022-0000

Uuid: uuid:88836faf-6750-41d2-8f9c-ba7c96a410c5

Urn: uri:88836faf-6750-41d2-8f9c-ba7c96a410c5

Pubs-id: pubs:654370 Item Description

Type: journal-article;

Version: Publisher's versionKeywords: constraint satisfaction satisfiability backdoor set parameterized complexity

Relationships





Autor: Gaspers, S - - - Misra, N - - - Ordyniak, S - - - Szeider, S - - - Živný, S - facultyOxford, MPLS, Computer Science fundingRoya

Fuente: https://ora.ox.ac.uk/objects/uuid:88836faf-6750-41d2-8f9c-ba7c96a410c5



DESCARGAR PDF




Documentos relacionados