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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-01785230
Contributor : Philippe Jégou <>
Submitted on : Wednesday, May 16, 2018 - 6:23:16 PM
Last modification on : Monday, March 30, 2020 - 8:42:14 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 1:44:11 AM

File

AAAI-2017-ElMouelhi.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01785230, version 1

Citation

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⟩

Share

Metrics

Record views

78

Files downloads

23