A BTP-Based Family of Variable Elimination Rules for Binary CSPs - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

A BTP-Based Family of Variable Elimination Rules for Binary CSPs

(1, 2)
1
2

Abstract

The study of broken-triangles is becoming increasingly ambitious , by both solving constraint satisfaction problems (CSPs) in polynomial time and reducing search space size through value merging or variable elimination. Considerable progress has been made in extending this important concept, such as dual broken-triangle and weakly broken-triangle, in order to maximize the number of captured tractable CSP instances and/or the number of merged values. Specifically, m-wBTP allows to merge more values than BTP. k-BTP, WBTP and m-BTP permit to capture more tractable instances than BTP. Here, we introduce a new weaker form of BTP, which will be called m-fBTP for flexible broken-triangle property. m-fBTP allows on the one hand to eliminate more variables than BTP while preserving satisfiability and on the other to define new bigger tractable class for which arc consistency is a decision procedure. Likewise, m-fBTP permits to merge more values than BTP but less than m-wBTP.
Fichier principal
Vignette du fichier
AAAI-2017-ElMouelhi.pdf (673.82 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01785230 , version 1 (16-05-2018)

Identifiers

  • HAL Id : hal-01785230 , version 1

Cite

Achref El Mouelhi. A BTP-Based Family of Variable Elimination Rules for Binary CSPs. Thirty-First AAAI Conference on Artificial Intelligence, Feb 2017, San Francisco, United States. ⟨hal-01785230⟩
45 View
12 Download

Share

Gmail Facebook Twitter LinkedIn More