Conference item icon

Conference item

Backdoors into heterogeneous classes of SAT and CSP

Abstract:

Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the c...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Association for the Advancement of Artificial Intelligence Publisher's website
Pages:
2652-2658
Publication date:
2014-06-21
Pubs id:
pubs:489688
URN:
uri:513b24b0-742c-43be-b0b6-2caf6d24a449
UUID:
uuid:513b24b0-742c-43be-b0b6-2caf6d24a449
Local pid:
pubs:489688
ISBN:
9781577356806

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP