Journal article icon

Journal article

On singleton arc consistency for CSPs defined by monotone patterns

Abstract:

Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of wh...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1007/s00453-018-0498-2

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Cooper, MC More by this author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
More from this funder
Funding agency for:
Zivny, S
More from this funder
Grant:
ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02
Publisher:
Springer US Publisher's website
Journal:
Algorithmica Journal website
Volume:
81
Issue:
4
Pages:
1699–1727
Publication date:
2018-08-13
Acceptance date:
2018-08-02
DOI:
EISSN:
1432-0541
ISSN:
0178-4617
Pubs id:
pubs:892209
URN:
uri:14d312ed-e35b-4e10-8c55-068b750604dd
UUID:
uuid:14d312ed-e35b-4e10-8c55-068b750604dd
Local pid:
pubs:892209

Terms of use


Metrics



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

TO TOP