HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Variable Elimination in Binary CSPs (Extended Abstract)

Abstract : We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each defines a novel tractable class. Using our variable elimination rules in preprocessing allowed us to solve more benchmark problems than without.
Document type :
Conference papers
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-02897892
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Tuesday, February 16, 2021 - 11:05:14 AM
Last modification on : Wednesday, March 23, 2022 - 3:08:49 AM
Long-term archiving on: : Monday, May 17, 2021 - 6:53:00 PM

File

0702.pdf
Files produced by the author(s)

Identifiers

Citation

Martin Cooper, Achref El Mouelhi, Cyril Terrioux. Variable Elimination in Binary CSPs (Extended Abstract). Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence , Jul 2020, Yokohama, France. pp.5035-5039, ⟨10.24963/ijcai.2020/702⟩. ⟨hal-02897892⟩

Share

Metrics

Record views

109

Files downloads

30