Variable and value elimination in binary constraint satisfaction via forbidden patterns. / Cohen, David; Cooper, Martin; Escamocher, Guillaume; Zivny, Stanislav.

In: Journal of Computer and System Sciences, Vol. 81, No. 7, 11.2015, p. 1127–1143.

Research output: Contribution to journal › Article › peer-review

Published

Standard

Variable and value elimination in binary constraint satisfaction via forbidden patterns. / Cohen, David; Cooper, Martin; Escamocher, Guillaume; Zivny, Stanislav.

In: Journal of Computer and System Sciences, Vol. 81, No. 7, 11.2015, p. 1127–1143.

Research output: Contribution to journal › Article › peer-review

Harvard

Cohen, D, Cooper, M, Escamocher, G & Zivny, S 2015, 'Variable and value elimination in binary constraint satisfaction via forbidden patterns', Journal of Computer and System Sciences, vol. 81, no. 7, pp. 1127–1143. https://doi.org/10.1016/j.jcss.2015.02.001

APA

Cohen, D., Cooper, M., Escamocher, G., & Zivny, S. (2015). Variable and value elimination in binary constraint satisfaction via forbidden patterns. Journal of Computer and System Sciences, 81(7), 1127–1143. https://doi.org/10.1016/j.jcss.2015.02.001

Vancouver

Cohen D, Cooper M, Escamocher G, Zivny S. Variable and value elimination in binary constraint satisfaction via forbidden patterns. Journal of Computer and System Sciences. 2015 Nov;81(7):1127–1143. https://doi.org/10.1016/j.jcss.2015.02.001

Author

Cohen, David ; Cooper, Martin ; Escamocher, Guillaume ; Zivny, Stanislav. / Variable and value elimination in binary constraint satisfaction via forbidden patterns. In: Journal of Computer and System Sciences. 2015 ; Vol. 81, No. 7. pp. 1127–1143.

BibTeX

@article{2d219ce82c454b2591351680cc54f472,
title = "Variable and value elimination in binary constraint satisfaction via forbidden patterns",
abstract = "Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (value elimination rule) allows the polynomial-time identification of certain variables (domain elements) whose elimination, without the introduction of extra compensatory constraints, does not affect the satisfiability of an instance. We show that there are essentially just four variable elimination rules and three value elimination rules defined by forbidding generic sub-instances, known as irreducible existential patterns, in arc-consistent CSP instances. One of the variable elimination rules is the already-known Broken Triangle Property, whereas the other three are novel. The three value elimination rules can all be seen as strict generalisations of neighbourhood substitution.",
author = "David Cohen and Martin Cooper and Guillaume Escamocher and Stanislav Zivny",
year = "2015",
month = nov,
doi = "10.1016/j.jcss.2015.02.001",
language = "English",
volume = "81",
pages = "1127–1143",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "7",

}

RIS

TY - JOUR

T1 - Variable and value elimination in binary constraint satisfaction via forbidden patterns

AU - Cohen, David

AU - Cooper, Martin

AU - Escamocher, Guillaume

AU - Zivny, Stanislav

PY - 2015/11

Y1 - 2015/11

N2 - Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (value elimination rule) allows the polynomial-time identification of certain variables (domain elements) whose elimination, without the introduction of extra compensatory constraints, does not affect the satisfiability of an instance. We show that there are essentially just four variable elimination rules and three value elimination rules defined by forbidding generic sub-instances, known as irreducible existential patterns, in arc-consistent CSP instances. One of the variable elimination rules is the already-known Broken Triangle Property, whereas the other three are novel. The three value elimination rules can all be seen as strict generalisations of neighbourhood substitution.

AB - Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (value elimination rule) allows the polynomial-time identification of certain variables (domain elements) whose elimination, without the introduction of extra compensatory constraints, does not affect the satisfiability of an instance. We show that there are essentially just four variable elimination rules and three value elimination rules defined by forbidding generic sub-instances, known as irreducible existential patterns, in arc-consistent CSP instances. One of the variable elimination rules is the already-known Broken Triangle Property, whereas the other three are novel. The three value elimination rules can all be seen as strict generalisations of neighbourhood substitution.

U2 - 10.1016/j.jcss.2015.02.001

DO - 10.1016/j.jcss.2015.02.001

M3 - Article

VL - 81

SP - 1127

EP - 1143

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 7

ER -

Find an expert

Computer Science home
Research
Profile
Researchers
Publications
Projects