Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Philippe Jégou Connect in order to contact the contributor
Submitted on : Wednesday, May 16, 2018 - 6:23:16 PM
Last modification on : Friday, October 22, 2021 - 3:36:15 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 1:44:11 AM


Files produced by the author(s)


  • HAL Id : hal-01785230, version 1


Achref 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⟩



Record views


Files downloads