OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Extending Broken Triangles and Enhanced Value-Merging

Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril Extending Broken Triangles and Enhanced Value-Merging. (2016) In: 22nd International Conference on Principles and Practice of Constraint Programming (CP 2016), 5 September 2016 - 9 September 2016 (Toulouse, France).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1007/978-3-319-44953-1_12


Broken triangles constitute an important concept not only for solving constraint satisfaction problems in polynomial time, but also for variable elimination or domain reduction by merging domain values. Specifically, for a given variable in a binary arc-consistent CSP, if no broken triangle occurs on any pair of values, then this variable can be eliminated while preserving satisfiability. More recently, it has been shown that even when this rule cannot be applied, it could be possible that for a given pair of values no broken triangle occurs. In this case, we can apply a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper we show that under certain conditions, and even if there are some broken triangles on a pair of values, these values can be merged without changing the satisfiability of the instance. This allows us to define a stronger merging operation and a new tractable class of binary CSP instances. We report experimental trials on benchmark instances.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in Volume 9892 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN: 978-3-319-44952-4 The original PDF is available at: http://link.springer.com/chapter/10.1007%2F978-3-319-44953-1_12
HAL Id:hal-01475026
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Other partners > Aix-Marseille Université - AMU (FRANCE)
Other partners > Arts et Métiers ParisTech (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Toulon - UTLN (FRANCE)
Laboratory name:
Deposited On:03 Feb 2017 10:25

Repository Staff Only: item control page