Geodesic
New schemes for simplifying binary constraint satisfaction problems
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1.

Voir la notice de l'article provenant de la source Episciences

Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivatedthe multitude of works that have been devoted to developing techniques that simplify CSP instances before or duringtheir resolution.The present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of valuedomains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrizedgeneralizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhoodsubstitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination,which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs byidentifying a new tractable class of binary CSP.
DOI : 10.23638/DMTCS-22-1-10
Classification : 68Q17, 68Q27, 68T20 
@article{DMTCS_2020_22_1_a15,
     author = {Naanaa, Wady},
     title = {New schemes for simplifying binary constraint satisfaction problems},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-10/}
}
TY  - JOUR
AU  - Naanaa, Wady
TI  - New schemes for simplifying binary constraint satisfaction problems
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-10/
DO  - 10.23638/DMTCS-22-1-10
LA  - en
ID  - DMTCS_2020_22_1_a15
ER  - 
%0 Journal Article
%A Naanaa, Wady
%T New schemes for simplifying binary constraint satisfaction problems
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-10/
%R 10.23638/DMTCS-22-1-10
%G en
%F DMTCS_2020_22_1_a15
Naanaa, Wady. New schemes for simplifying binary constraint satisfaction problems. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi : 10.23638/DMTCS-22-1-10. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-10/

Cité par Sources :