Skip to Main content Skip to Navigation
Conference papers

Sur la complexité des algorithmes de backtracking et quelques nouvelles classes polynomiales pour CSP

Abstract : The question of tractable classes of constraint satisfaction problems (CSPs) has been studied for a long time, and is now a very active research domain. However, studies of tractable classes are typically very theoretical. They usually introduce classes of instances together with polynomial time algorithms for recognizing and solving them, and the algorithms can be used only for the new class. In this paper, we address the issue of tractable classes of CSPs from a di erent perspective. We investigate the complexity of classical, generic algorithms for solving CSPs (such as Forward Checking). We introduce a new parameter for measuring their complexity and derive new complexity bounds. By relating the com- plexity of CSP algorithms to graph-theoretic parameters, our analysis allows us to point at new tractable classes, which can be solved directly by the usual CSP algorithms in polynomial time, and without the need to recognize the classes in advance.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00830458
Contributor : Ist Inria Saclay Connect in order to contact the contributor
Submitted on : Wednesday, June 5, 2013 - 10:31:00 AM
Last modification on : Saturday, June 25, 2022 - 7:48:46 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 5:06:10 PM

File

paper_16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00830458, version 1

Citation

Achref El Mouelhi, Philippe Jégou, Cyril Terrioux, Bruno Zanuttini. Sur la complexité des algorithmes de backtracking et quelques nouvelles classes polynomiales pour CSP. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. ⟨hal-00830458⟩

Share

Metrics

Record views

464

Files downloads

620