. .. Csp,

.. .. Redémarrage,

. .. , 94 2.2.5.3 Comparaison en termes de bornes de complexité et de performances

. Problème and . .. #csp,

.. .. Formalisme,

. .. Méthodes-de-résolution,

. Recherche and . .. #ebtd, 210 6.3.1 Comptage aveugle vs comptage conscient

.. .. Fondements,

.. .. ,

.. .. Conclusion,

R. Plus and . Au-comptage, #EBTD la version présentée dans l'algorithme 6.2 est basée sur un simple algorithme de retourarrière chronologique (BT ). Toutefois, dans les expérimentations fournies dans la section suivante, nous considérons un algorithme plus puissant qui est RF L. Ainsi, #EBT D choisit en premier la prochaine variable xà assigner, vol.46

. Après and . Valeur-v-de-d-x-selon-l, heuristique de choix de valeur (lignes 51-52) et l'assigneà la variable x. Si la nouvelle affectation est cohérente vis-à-vis des contraintes initiales de C et des nogoods structurels de N d (ligne 53), la recherche continue en choisissant une nouvelle variable et en effectuant une nouvelle affectation. Sinon, #EBT D essaye d'assignerà x une autre valeur de D x

#. Lorsque, . Instancié-d-;-de-p-l-|a-;-=, and . En, moment où il est certain que cette affectation admet une extension cohérente sur tout le problème, il vise ensuiteà compter le nombre de solutions de chaque sousproblème enraciné en chaque cluster fils du cluster courant comme ferait #BT D. Plus précisément, si E i est, par exemple, le cluster courant dans la figure 6.1 (E g et E h sont déjà instanciés), son but est de calculer le nombre de solutions de P j |A, Similairement, #BT D enregistrerait les #goods correspondantsà chaque sousproblème

. La-différence-principale-entre-#ebt-d, ]. #bt-d-réside-dans-l-;-e-i-?-e-j, and . |a[e-i-?-e-l-]-et-de-p-n-|a, #EBT D ne procède pas ainsi. Il vise au contraireàéviter les inconvénients de cette approche décrits dans la partie 6.2.2. #EBT D explore alors les clusters fils différemment. Plus précisément, il viseà garantir qu'il ne compte exactement le nombre de solutions du sous-problème enraciné en un cluster fils que s'il existe une solution globale du problème compatible avec l'affectation courante, c'est-à-dire une extension de l'affectation courante qui s'étend sur toutes les variables du problème. Ce faisant, le good exact ainsi enregistré est nécessairement utilisé au moins une fois. Pour illustrer ce principe, dans la figure 6.1, après l'affectation du cluster E i , #EBT D essaye d'instancier, par ordre, les clusters E j , E k , E l , E m et E n (#EBT D explore, dans ce cas, les clusters fils de E i dans l'ordre E j , E l et E n )

. ?-e-bt, ligne 56) suspend l'énumération des solutions relativesà E i lorsqu'un nogood de E p(?) par rapportà E ? est enregistré avec E ? est un cluster exploré après E i . Dans ce cas, E bt = E p(?) et la recherche fait retour-arrière vers le cluster E p(?)

. #ebt-d-considère-chaque-cluster-fils-de-e-i, -16). Si A[E i ? E j ] correspondà un exact good (ligne 10), le good est exploité et la recherche

. #ebt-d-utilise-deux-piles-locales-z-inconnu, Il ajouteà Z età Z inconnu chaque cluster fils E j de E i pour lequel A[E i ? E j ] ne correspond pas nià un good

?. Pour-chaque-cluster-de-z-good, . De-solutions-de-p-j-|a[e-i-?-e-j-]-est-calculé, and . Ultérieurement, Au contraire, si A n'a pas puêtreétendue au sous-problème enraciné en E j , A[E p(j) ? E j ] est enregistrée comme un nogood (lignes 31-35). Il està noter que E p(j) n'est pas forcément E i . Les lignes 27 et 33 permettent finalement de supprimer de la pile

#. Concernant, nous distinguons deux phases qui s'alternent

, ? La première phase viseà s'assurer que pour une solution partielle, il existe une solution globale, c'est-à-dire une affectation qui s'étend de fa¸con cohérente sur toutes les variables du problème

?. La and . Consisteàénumérer, une fois la présence d'une solution globale garantie, l'ensemble des extensions cohérentes d'une affectation induisant un sous-problème pour ce dernier

, Ces deux phases garantissent que, chaque fois que le nombre de solutions d'un sousproblème est calculé, celui-ci est exploité pour le calcul du nombre de solutions du problème. Nous allons donc maintenant démontrer que #EBT D est capable de calculer le nombre exact de solutions d'un problème tout en garantissant d'éviter certains calculs inutiles au sensévoqué précédemment

?. V-e-i,

?. Desc, j ) : l'ensemble des variables de Desc(E j ) sans compter les variables de E i ? E j tel que E j est un cluster fils de E i pour lequel A

. ?-g-=,

). Si-a[e-i-?-e-j-]-?-g-=-(e-j and L. Good-a[e-i-?-e-j, est exploité selon la définition d'un good exact et le sous-problème correspondant n'est pas visité. Si A[E i ? E j ] est un good partiel, le sous-problème enraciné en E j n'est pas exploré lors de la recherche d'une solution globale (vu qu'au moins une extension cohérente existe pour ce sousproblème). Cependant, une fois une solution globale trouvée, il sera visité afin de calculer #sol E j . Sinon, A[E i ? E j ] est inconnu et le sous-problème correspondant doitêtre exploré pour déterminer si une solution globale existe

?. Desc, ? E k ) : l'ensemble des variables de Desc(E k ) sans compter les variables de E p(k) ? E k tel que E k ? Z. Le cluster E k est

Z. V-e-i, A. Et-nous-considérons-la-propriété-p(v-ar(v-e-i, Z. , A. G-d-))-définie-par, ;. #ebt-d(p et al., N d ) retourne une paire (#sol, E bt ) où #sol est le nombre exact de solutions de P i |A

R. Plus and . Au-comptage-:-#ebtd-e-i-=-e-p, ligne 32), les fils de E i sont supprimés de la pile Z vu que leur exploration est désormais inutile (ligne 33). Ainsi, #EBT D retourne (0, E i ) puisqu'il n'existe aucune extension possible de A sur les variables de Desc(E j ) et le cluster E i doitêtre modifié (ligne 34). Sinon, E i = E p(j) et la recherche doit faire un retour-arrière plus loin. Ainsi, #EBT D retourne (#sol, E p(j ) avec #sol une borne inférieure sur le nombre de solutions de P i |A

, Si #sol E j > 0 et E bt = E j alors le nombre de solutions retourné est nécessairement une borne inférieure sur le nombre de solutions P j |A

E. and ]. ,

, est alors enregistrée comme un good partiel qui peutêtre exploité ultérieurement, si nécessaire. Le raisonnement des lignes 26-29 est similaireà celui pour les lignes 32-35

L. Ainsi, Z. Propriété-p(v-ar(v-e-i, and A. ,

*. Si-#sol-e-j->-0-et-e-bt-=-e-j-alors-le-nombre-de-solutions-retourné-est-celui-du-nombre-exact-de-solutions-de-p-j-|a, A[E p(j) ? E j ] est enregistrée comme un good exact.À ce niveau, Z est vide puisque sinon l'exploration des clusters de Z aurait continué jusqu'à atteindre le dernier cluster. En d'autres termes, l'enregistrement des goods exacts ne peut pas se faire avant que tous les clusters de Z ne soient explorés. En outre, sachant que la traversée de la décomposition se fait grâceà une pile, si A[E p(j) ? E j ] est enregistrée comme un good exact alors tous les clusters E k insérés dans Z avant E j sont déjà exhaustivement explorés et l'affectation A

Z. V-e-i and A. , est alors valide pour Z = ? pour les trois sous-cas possibles.À la ligne 36, Z = ?, une solution globale aété déjà trouvée et pour chaque cluster fils E j ? Z inconnu , #sol E j est calculé et #sol est mis a jour (ligne 37). Si Z good ? = ?

V. Si, Z. Ar(v-e-j, A. G-d-)-?-v-ar(v-e-i, Z. , A. V-e-j et al., d )) est valide. Sinon, nous avons V AR, par hypothèse d'induction

V. Ar(v-e-i, Z. , A. V-e-j, Z. , and A. , est valide. Par définition d'un good partiel, P j |A[E i ?E j ] a au moins une seule solution. Comme Z est vide (une solution globale existe), l'appel récursifà #EBT D retourne nécessairement le nombre exact de solutions de P j |A

, Une fois, tous les clusters fils E j considérés, #sol est mis-à-jour et #EBT D retourne (#sol, E i )

. En-conséquence, Z. La-propriété-p(v-ar(v-e-i, and A. G-d-))-est-valide-pour-v-e-i-=-?,

V. Ar(v-e-i, Z. , A. G-d-))-est-valide-;-v-e-j, Z. , and A. , En effet, dans le cas où V E i = ?, l'appel récursif fait par #EBT D considère l'ensemble V E i \{x} qui contient strictement moins de variables que V E i (une variable en moins). Ainsi, la taille de V AR est désormais plus petite, Si V E i = ?, comme nous l'avons déjà vu, les appels récursifs aux lignes 20 et 41 garantissent que V AR

V. Ar(v-e-i, Z. , and A. , Un extension générale de ces travaux est d'aller au-delà de BT D. En effet, bien que la méthode BT D soit ici la méthode référence employée pourévaluer l'intérêt des nouvelles méthodes de calcul ou d'exploitation de la décomposition arborescente, les objectifs de la thèse ne se limitent pasà l'amélioration de BT D. Ainsi, une extension générale de ce travail est de l'appliquer aux autres méthodes structurelles comme celles basées sur la décomposition hyperarborescente, En cas d'égalité, nous exploitons le fait que pour l'appel suivant par ce dernier, voire meilleures. Finalement, l'importance de la minimisation de la largeur w + aété soulignée pour le comptage contrairement aux problèmes de décision et d'optimisation, 1987.

. Dermaku, En conclusion, dans cette thèse, notre ambition est d'intégrer la brique structurelle aux briques standards des solveurs actuels. Nous avons tenté d'améliorer les méthodes structurelles et de montrer qu'elles peuventêtre compétitives vis-à-vis des méthodes classiques. Notre ambition est d'autant plus réaliste que l'intégration des méthodes telles que BT D s'avèreêtre d'une simplicité remarquable, Cette approche est particulièrement justifiée par les similitudes existantes entre les différentes méthodes notamment en termes de la liberté restreinte accordéeà l'heuristique de choix de variables, 2006.

, Choco : an open source java constraint programming library

, Luebeck university implementation for pace competition, Csp competition, 2008.

, Utrecht university implementation for pace competition, 2017 XCSP3 Competition, 2017.

I. Adler, G. Gottlob, and M. Grohe, Hypertree width and related hypergraph invariants, European Journal of Combinatorics, pp.2167-2181, 2007.
URL : https://hal.archives-ouvertes.fr/hal-01184381

D. Allouche, S. D. Givry, G. Katsirelos, T. Schiex, and M. Zytnicki, Anytime hybrid best-first search with tree decomposition for weighted CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.12-29, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01198361

E. Amir, Efficient approximation for triangulation of minimum treewidth, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.7-15, 2001.

E. Amir, Approximation algorithms for treewidth. Algorithmica, pp.448-479, 2010.

O. Angelsmark and P. Jonsson, Improved algorithms for counting solutions in constraint satisfaction problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.81-95, 2003.

U. Apsel and R. I. Brafman, Lifted MEU by Weighted Model Counting, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.1861-1867, 2012.

K. Apt, Principles of constraint programming, 2003.

S. Arnborg, D. Corneil, and A. Proskurowski, Complexity of finding embeddings in ak-tree, SIAM Journal on Algebraic Discrete Methods, pp.277-284, 1987.

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, pp.308-340, 1991.

M. Aschinger, C. Drescher, G. Gottlob, P. Jeavons, and E. Thorstensen, Structural decomposition methods and what they are good for, Symposium on Theoretical Aspects of Computer Science (STACS), pp.12-28, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00573592

P. Austrin, T. Pitassi, and Y. Wu, Inapproximability of treewidth, one-shot pebbling, and related layout problems, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.13-24, 2012.

F. Bacchus, S. Dalmao, and T. Pitassi, Value elimination : Bayesian inference via backtracking search, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.20-28, 2002.

F. Bacchus and A. Grove, On the forward checking algorithm, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.292-309, 1995.

E. H. Bachoore and H. L. Bodlaender, New upper bound heuristics for treewidth, International Workshop on Experimental and Efficient Algorithms, pp.216-227, 2005.

E. H. Bachoore and H. L. Bodlaender, A branch and bound algorithm for exact, upper, and lower bounds on treewidth, International Conference on Algorithmic Applications in Management (AAIM), pp.255-266, 2006.

J. Baget and Y. S. Tognetti, Backtracking through biconnected components of a constraint graph, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.291-296, 2001.

O. Bailleux and J. Chabrier, Approximate resolution of hard numbering problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.169-174, 1996.

L. Baptista, I. Lynce, and J. P. Silva, Complete search restart strategies for satisfiability, IJCAI Workshop on Stochastic Search Algorithms, 2001.

J. R. Bayardo and J. D. Pehoushek, Counting models using connected components, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.157-162, 2000.

R. J. Bibliographie-bayardo and D. P. Miranker, A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.298-304, 1996.

P. V. Beek, Backtracking search algorithms, Foundations of Artificial Intelligence, pp.85-134, 2006.

C. Beeri, R. Fagin, D. Maier, Y. , and M. , On the desirability of acyclic database schemes, Journal of the ACM (JACM), pp.479-513, 1983.

N. Beldiceanu, M. Carlsson, S. Demassey, and T. Petit, Global constraint catalogue : Past, present and future, Constraints, pp.21-62, 2007.

N. Beldiceanu, M. Carlsson, R. , and J. , Global constraint catalog, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00485396

J. Berg and M. Järvisalo, SAT-Based Approaches to Treewidth Computation : An Evaluation, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.328-335, 2014.

C. Berge, Graphes et hypergraphes, 1973.

A. Berry, J. R. Blair, P. Heggernes, P. , and B. W. , Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, pp.287-298, 2004.

A. Berry, J. Bordat, P. Heggernes, G. Simonet, and Y. Villanger, A wide-range algorithm for minimal triangulation from an arbitrary ordering, Journal of Algorithms, pp.33-66, 2006.
URL : https://hal.archives-ouvertes.fr/lirmm-00268438

A. Berry, P. Heggernes, and G. Simonet, The minimum degree heuristic and the minimal triangulation process, International Workshop on Graph-Theoretic Concepts in Computer Science, pp.58-70, 2003.
URL : https://hal.archives-ouvertes.fr/lirmm-00191916

A. Berry, P. Heggernes, and Y. Villanger, A vertex incremental approach for dynamically maintaining chordal graphs, International Symposium on Algorithms and Computation (ISAAC), pp.47-57, 2003.

U. Bertele and F. Brioschi, Nonserial dynamic programming, 1972.

C. Bessiere, Arc-consistency and arc-consistency again, Artificial intelligence, pp.179-190, 1994.
URL : https://hal.archives-ouvertes.fr/lirmm-02310614

C. Bessiere, Constraint propagation. Foundations of Artificial Intelligence, pp.29-83, 2006.
URL : https://hal.archives-ouvertes.fr/lirmm-00117128

C. Bessière, A. Chmeiss, and L. Sais, Neighborhood-based variable ordering heuristics for the constraint satisfaction problem, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.565-569, 2001.

C. Bessiere, E. Hebrard, B. Hnich, W. , and T. , The complexity of reasoning with global constraints, Constraints, pp.239-259, 2007.
URL : https://hal.archives-ouvertes.fr/lirmm-00195881

C. Bessière, P. Meseguer, E. C. Freuder, and J. Larrosa, On forward checking for non-binary constraint satisfaction, Artificial Intelligence, pp.205-224, 2002.

C. Bibliographie-bessiere and J. Régin, MAC and combined heuristics : Two reasons to forsake FC (and CBJ ?) on hard problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.61-75, 1996.

C. Bessiere and J. Régin, Arc consistency for general constraint networks : preliminary results, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1997.

C. Bessière and J. Régin, Refining the Basic Constraint Propagation Algorithm, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.309-315, 2001.

C. Bessière, J. Régin, R. H. Yap, and Y. Zhang, An optimal coarse-grained arc consistency algorithm, Artificial Intelligence, pp.165-185, 2005.

W. Bibel, Constraint satisfaction from a deductive viewpoint, Artificial Intelligence, pp.401-413, 1988.

A. Biere, Adaptive restart control for conflict driven SAT solvers, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), 2008.

A. Biere, M. Heule, and H. Van-maaren, Handbook of satisfiability, 2009.

E. Birnbaum and E. L. Lozinskii, The good old Davis-Putnam procedure helps counting models, Journal of Artificial Intelligence Research, pp.457-477, 1999.

J. R. Bitner and E. M. Reingold, Backtrack programming techniques. Communications of the ACM, pp.651-656, 1975.

J. R. Blair, P. Heggernes, and J. A. Telle, A practical algorithm for making filled graphs minimal, Theoretical Computer Science, pp.125-141, 2001.

L. Blet, Configuration automatique d'un solveur generique integrant des techniques de decomposition arborescente pour la resolution de problemes de satisfaction de contraintes, 2015.
URL : https://hal.archives-ouvertes.fr/tel-01214086

H. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on computing, pp.1305-1317, 1996.

H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov et al., A c k n 5-Approximation Algorithm for Treewidth, SIAM Journal on Computing, pp.317-378, 2016.

H. L. Bodlaender, F. V. Fomin, A. M. Koster, D. Kratsch, and D. M. Thilikos, On exact algorithms for treewidth, Proceedings The Annual European Symposium on Algorithms (ESA), pp.672-683, 2006.
URL : https://hal.archives-ouvertes.fr/lirmm-00804792

H. L. Bodlaender, F. V. Fomin, A. M. Koster, D. Kratsch, and D. M. Thilikos, On exact algorithms for treewidth, ACM Transactions on Algorithms, p.12, 2012.
URL : https://hal.archives-ouvertes.fr/lirmm-00804792

H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, pp.238-255, 1995.

H. L. Bodlaender and A. M. Koster, Treewidth computations I. Upper bounds. Information and Computation, pp.259-275, 2010.

H. L. Bodlaender and A. M. Koster, Treewidth computations II. Lower bounds. Information and Computation, pp.1103-1119, 2011.

J. A. Bondy and U. S. Murty, Graph theory with applications, 1976.

G. Boole, An investigation of the laws of thought, 1854.

V. Bouchitté, D. Kratsch, H. Müller, and I. Todinca, On treewidth approximations, Discrete Applied Mathematics, pp.183-196, 2004.

V. Bouchitté and I. Todinca, Treewidth and minimum fill-in : Grouping the minimal separators, SIAM Journal on Computing, pp.212-232, 2001.

V. Bouchitté and I. Todinca, Listing all potential maximal cliques of a graph, Theoretical Computer Science, pp.17-32, 2002.

F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais, Boosting Systematic Search by Weighting Constraints, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.146-150, 2004.

F. Boussemart, C. Lecoutre, and C. Piette, XCSP3 : An integrated format for benchmarking combinatorial constrained problems. arXiv, 2016.

A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph classes : a survey, 1999.

D. Brélaz, New methods to color the vertices of a graph, Communications of the ACM, pp.251-256, 1979.

R. E. Bryant, Graph-based algorithms for boolean function manipulation, pp.677-691, 1986.

B. Bui-xuan, J. Telle, and M. Vatshelle, Boolean-width of graphs, Theoretical Computer Science, pp.5187-5204, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00640644

A. A. Bulatov, The complexity of the counting constraint satisfaction problem, The International Colloquium on Automata, Languages, and Programming (ICALP), pp.646-661, 2008.

A. A. Bulatov and V. Dalmau, Towards a dichotomy theorem for the counting constraint satisfaction problem, Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pp.562-571, 2003.

P. Buneman, A characterisation of rigid circuit graphs. Discrete mathematics, pp.205-212, 1974.

R. Burton and J. E. Steif, Non-uniqueness of measures of maximal entropy for subshifts of finite type. Ergodic Theory and Dynamical Systems, pp.213-235, 1994.

B. Cabon, S. D. Givry, L. Lobjois, T. Schiex, and J. P. Warners, Radio link frequency assignment, Constraints, pp.79-89, 1999.

H. Cambazard, T. Hadzic, and B. Sullivan, Knowledge Compilation for Itemset Mining, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.1109-1110, 2010.

M. Bibliographie-chavira and A. Darwiche, On probabilistic inference by weighted model counting, Artificial Intelligence, pp.772-799, 2008.

X. Chen, A Theoretical Comparison of Selected Csp Solving and Modeling Techniques, 2000.

A. Chmeiss and P. Jégou, Efficient path-consistency propagation, International Journal on Artificial Intelligence Tools, pp.121-142, 1998.

A. Choi, D. Kisa, and A. Darwiche, Compiling probabilistic graphical models using sentential decision diagrams, Proceedings of European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pp.121-132, 2013.

F. Clautiaux, A. Moukrim, S. Nègre, and J. Carlier, Heuristic and metaheuristic methods for computing graph treewidth. RAIRO-Operations Research, pp.13-26, 2004.

D. Cohen, P. Jeavons, and M. Gyssens, A unified theory of structural tractability for constraint satisfaction problems, Journal of Computer and System Sciences, pp.721-743, 2008.

D. A. Cohen, P. Jeavons, and M. Gyssens, A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.72-77, 2005.

S. A. Cook, The complexity of theorem-proving procedures, Proceedings of the Annual ACM symposium on Theory of computing, pp.151-158, 1971.

M. Cooper and T. Schiex, Arc consistency for soft constraints. Artificial Intelligence, pp.199-227, 2004.

M. C. Cooper, An optimal k-consistency algorithm, Artificial Intelligence, pp.89-95, 1989.

M. C. Cooper, Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems, pp.311-342, 2003.

M. C. Cooper, S. D. Givry, M. Sanchez, T. Schiex, and M. Zytnicki, Virtual Arc Consistency for Weighted CSP, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.253-258, 2008.

M. C. Cooper, S. D. Givry, M. Sánchez, T. Schiex, M. Zytnicki et al., Soft arc consistency revisited, Artificial Intelligence, pp.449-478, 2010.

M. C. Cooper, S. D. Givry, and T. Schiex, Optimal Soft Arc Consistency, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.68-73, 2007.

B. Courcelle, The monadic second order theory of Graphs I : Recognisable 662 sets of finite graphs. Information and Computation, p.663, 1990.

B. Courcelle and S. Olariu, Upper bounds to the clique width of graphs, Discrete Applied Mathematics, pp.77-114, 2000.

D. Dahlhaus, Minimal elimination ordering inside a given chordal graph, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, pp.132-143, 1997.

A. Bibliographie-darwiche, Decomposable negation normal form, Journal of the ACM (JACM), pp.608-647, 2001.

A. Darwiche, On the tractable counting of theory models and its application to truth maintenance and belief revision, Journal of Applied Non-Classical Logics, pp.11-34, 2001.

A. Darwiche, Recursive conditioning, Artificial Intelligence, pp.5-41, 2001.

A. Darwiche, New advances in compiling CNF into decomposable negation normal form, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.328-332, 2004.

A. Darwiche, Modeling and reasoning with Bayesian networks, 2009.

A. Darwiche, SDD : A new canonical representation of propositional knowledge bases, SDD : A new canonical representation of propositional knowledge bases, p.819, 2011.

A. Darwiche and P. Marquis, A perspective on knowledge compilation, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.175-182, 2001.

A. Darwiche and P. Marquis, A knowledge compilation map, Journal of Artificial Intelligence Research, pp.229-264, 2002.

J. Davies and F. Bacchus, Using more reasoning to improve #SAT solving, Proceedings of the National Conference on Artificial Intelligence (AAAI), p.185, 2007.

M. Davis, G. Logemann, and D. Loveland, A machine program for theoremproving, Communications of the ACM, pp.394-397, 1962.

R. Debruyne and C. Bessiere, From restricted path consistency to max-restricted path consistency, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.312-326, 1997.

R. Debruyne and C. Bessiere, Some practicable filtering techniques for the constraint satisfaction problem, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1997.

R. Dechter, Learning while searching in constraint-satisfaction problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), 1986.

R. Dechter, Enhancement schemes for constraint processing : Backjumping, learning, and cutset decomposition, Artificial Intelligence, pp.273-312, 1990.

R. Dechter, Constraint networks, 1992.

R. Dechter, Topological parameters for time-space tradeoff, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.220-227, 1996.

R. Dechter, Bucket elimination : A unifying framework for reasoning, Artificial Intelligence, pp.41-85, 1999.

R. Bibliographie-dechter, Constraint processing, 2003.

R. Dechter, Tractable structures for constraint satisfaction problems, Foundations of Artificial Intelligence, pp.209-244, 2006.

R. Dechter, Reasoning with probabilistic and deterministic graphical models : Exact algorithms, Synthesis Lectures on Artificial Intelligence and Machine Learning, pp.1-191, 2013.

R. Dechter and Y. E. Fattah, Topological Parameters for Time-space Tradeoff, Artificial Intelligence, pp.93-118, 2001.

R. Dechter and R. Mateescu, The impact of AND/OR search spaces on constraint satisfaction and counting, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.731-736, 2004.

R. Dechter and R. Mateescu, AND/OR search spaces for graphical models. Artificial intelligence, pp.73-106, 2007.

R. Dechter and I. Meiri, Experimental evaluation of preprocessing techniques in constraint satisfaction problems, 1989.

R. Dechter and I. Meiri, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Artificial Intelligence, pp.211-241, 1994.

R. Dechter and J. Pearl, The cycle-cutset method for improving search performance in AI applications, 1986.

R. Dechter and J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial intelligence, pp.1-38, 1987.

R. Dechter and J. Pearl, Tree clustering for constraint networks, Artificial Intelligence, pp.353-366, 1989.

J. Demeulenaere, R. Hartert, C. Lecoutre, G. Perez, L. Perron et al., Compact-table : Efficiently filtering table constraints with reversible sparse bit-sets, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.207-223, 2016.

M. J. Dent and R. E. Mercer, Minimal forward checking, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.432-438, 1994.

A. Dermaku, T. Ganzow, G. Gottlob, B. Mcmahan, N. Musliu et al., Heuristic methods for hypertree decomposition, Proceedings of the Mexican International Conference on Artificial Intelligence (MICAI), pp.1-11, 2008.

R. Diestel and M. Müller, Connected tree-width. Combinatorica, 2017.

F. J. Díez, Local conditioning in Bayesian networks, Artificial Intelligence, pp.1-20, 1996.

G. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, vol.25, pp.71-76, 1961.

C. Bibliographie-domshlak and J. Hoffmann, Fast Probabilistic Planning through Weighted Model Counting, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp.243-252, 2006.

D. Dubois, H. Fargier, and H. Prade, The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction, Proceedings of the International Conference on Fuzzy Systems, pp.1131-1136, 1993.

M. Dyer and D. Richerby, An effective dichotomy for the counting constraint satisfaction problem, SIAM Journal on Computing, pp.1245-1274, 2013.

N. Eén and N. Sörensson, An extensible SAT-solver, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.502-518, 2003.

S. Even, Graph algorithms, 1979.

H. Fargier and J. Lang, Uncertainty in constraint satisfaction problems : a probabilistic approach, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pp.97-104, 1993.

H. Fargier, J. Lang, R. Martin-clouaire, and T. Schiex, A constraint satisfaction framework for decision under uncertainty, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.167-174, 1995.

H. Fargier, J. Lang, and T. Schiex, Selecting preferred solutions in fuzzy constraint satisfaction problems, Proceedings of the European Congress on Fuzzy and Intelligent Technologies (EUFIT), 1993.

H. Fargier and P. Marquis, Knowledge Compilation Properties of Trees-of-BDDs, Revisited, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.772-777, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00866834

A. Favier, S. D. Givry, and P. Jégou, Exploiting Problem Structure for Solution Counting, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.335-343, 2009.

U. Feige, M. Hajiaghayi, and J. R. Lee, Improved approximation algorithms for minimum weight vertex separators, SIAM Journal on Computing, pp.629-657, 2008.

M. R. Fellows and R. G. Downey, , 1999.

J. Flum and M. Grohe, Parameterized complexity theory, 2006.

F. Fomin, D. Kratsch, and I. Todinca, Exact (exponential) algorithms for treewidth and minimum fill-in, The International Colloquium on Automata, Languages, and Programming (ICALP), pp.568-580, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00085561

F. V. Fomin and Y. Villanger, Treewidth computation and extremal combinatorics, Combinatorica, pp.289-308, 2012.

E. Freuder and M. Quinn, Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.1076-1078, 1985.

E. C. Bibliographie-freuder, Synthesizing constraint expressions, Communications of the ACM, pp.958-966, 1978.

E. C. Freuder, A sufficient condition for backtrack-free search, Journal of the ACM (JACM), pp.24-32, 1982.

E. C. Freuder, Complexity of K-Tree Structured Constraint Satisfaction Problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), 1990.

E. C. Freuder and C. Elfe,

D. , Neighborhood inverse consistency preprocessing, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.202-208, 1996.

E. C. Freuder and B. Sullivan, Grand challenges for constraint programming, Constraints, pp.150-162, 2014.

E. C. Freuder and R. J. Wallace, Partial constraint satisfaction. Artificial Intelligence, pp.21-70, 1992.

E. C. Freuder and R. J. Wallace, Generalizing Inconsistency Learning for Constraint Satisfaction, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.563-571, 1995.

D. Frost and R. Dechter, Dead-end driven learning, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.294-300, 1994.

D. Frost and R. Dechter, Look-ahead value ordering for constraint satisfaction problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.572-578, 1995.

A. S. Fukunaga, Complete restart strategies using a compact representation of the explored search space, IJCAI Workshop on Stochastic Search Algorithms, 2003.

D. Fulkerson and O. Gross, Incidence matrices and interval graphs, Pacific journal of mathematics, pp.835-855, 1965.

J. Gajarsk?, M. Lampis, and S. Ordyniak, Parameterized Algorithms for Modular-Width, International Symposium IPEC, pp.163-176, 2013.

D. Gale and M. Sotomayor, Semiring-based constraint solving and optimization, American Mathematical Monthly, pp.261-268, 1985.

J. Gaschnig, Performance measurement and analysis of certain search algorithms, 1979.

F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B, pp.47-56, 1974.

P. Geelen, Dual Viewpoint Heuristics for, Proceedings of the European Conference on Artificial Intelligence (ECAI), vol.92, pp.31-35, 1992.

I. P. Gent, C. Jefferson, M. , and I. , Minion : A fast scalable constraint solver, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.98-102, 2006.

I. P. Bibliographie-gent, C. Jefferson, I. Miguel, and P. Nightingale, Data structures for generalised arc consistency for extensional constraints, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.191-197, 2007.

J. Gergov and C. Meinel, Efficient Boolean Manipulation with OBDD's Can be Extended to FBDD's. Transactions on Computers, pp.1197-1209, 1994.

M. L. Ginsberg, Dynamic backtracking, Journal of Artificial Intelligence Research (JAIR), pp.25-46, 1993.

S. D. Givry, F. Heras, M. Zytnicki, and J. Larrosa, Existential arc consistency : Getting closer to full arc consistency in weighted CSPs, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), vol.5, pp.84-89, 2005.

S. D. Givry, T. Schiex, and G. Verfaillie, Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.22-27, 2006.

G. Glorian, J. M. Lagniez, F. Boussemart, C. Lecoutre, and B. Mazure, Combinaison de nogoods extraits au redémarrage, Actes des Journées Francophones de Programmation par Contraintes (JFPC), pp.55-64, 2017.

V. Gogate and R. Dechter, A complete anytime algorithm for treewidth, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.201-208, 2004.

V. Gogate and R. Dechter, Approximate counting by sampling the backtrackfree search space, Proceedings of the National Conference on Artificial Intelligence (AAAI), p.198, 2007.

V. Gogate and R. Dechter, Approximate solution sampling (and counting) on and/or spaces, Lecture Notes in Computer Science, p.534, 2008.

S. W. Golomb and L. D. Baumert, Backtrack programming, Journal of the ACM (JACM), pp.516-524, 1965.

M. C. Golumbic, Algorithmic graph theory and perfect graphs, 2004.

C. P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman, From Sampling to Model Counting, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.2293-2299, 2007.

C. P. Gomes, A. Sabharwal, and B. Selman, Model counting : A new strategy for obtaining good bounds, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.54-61, 2006.

C. P. Gomes, B. Selman, N. Crato, and H. Kautz, Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, Journal of automated reasoning, pp.67-100, 2000.

C. P. Gomes, B. Selman, and H. Kautz, Boosting combinatorial search through randomization, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.431-437, 1998.

C. P. Bibliographie-gomes, W. J. Van-hoeve, A. Sabharwal, and B. Selman, Counting CSP solutions using generalized XOR constraints, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.204-209, 2007.

G. Gottlob, M. Hutle, and F. Wotawa, Combining hypertree, bicomp, and hinge decomposition, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.161-165, 2002.

G. Gottlob, N. Leone, and F. Scarcello, Hypertree decompositions and tractable queries, Proceedings of the ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp.21-32, 1999.

G. Gottlob, N. Leone, and F. Scarcello, A comparison of structural CSP decomposition methods, Artificial Intelligence, pp.243-282, 2000.

M. H. Graham, On the universal relation, 1980.

M. Grohe and D. Marx, Constraint solving via fractional edge covers, Proceedings of the annual ACM-SIAM symposium on Discrete algorithm, pp.289-298, 2006.

M. Grohe and D. Marx, Constraint solving via fractional edge covers, ACM Transactions on Algorithms, p.4, 2014.

M. Gyssens, P. Jeavons, and D. Cohen, Decomposing constraint satisfaction problems using database techniques, Artificial intelligence, pp.57-89, 1994.

M. Gyssens and J. Paredaens, A Decomposition Methodology for Cyclic Databases. Advances in data base theory, pp.85-122, 1982.

Z. Habbas, K. Amroun, and D. Singer, Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints. RAIRO-Operations Research, pp.241-267, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01277953

A. Hajnal and J. Surányi, Über die Auflösung von Graphen in vollständige Teilgraphen, Ann. Univ. Sci. Budapest, Eötvös Sect. Math, pp.113-121, 1958.

M. Hamann and D. Weißauer, Bounding connected tree-width, SIAM Journal on Discrete Mathematics, pp.1391-1400, 2016.

T. Hammerl, N. Musliu, and W. Schafhauser, Metaheuristic algorithms and tree decomposition, Handbook of Computational Intelligence, pp.1255-1270, 2015.

C. Han and C. Lee, Comments on Mohr and Henderson's path consistency algorithm, Artificial Intelligence, pp.125-130, 1988.

R. M. Haralick and G. L. Elliott, Increasing tree search efficiency for constraint satisfaction problems, Artificial intelligence, pp.263-313, 1980.

W. D. Harvey, Nonsystematic backtracking search, 1995.

W. D. Harvey and M. L. Ginsberg, Limited discrepancy search, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.607-615, 1995.

P. Heggernes, Minimal triangulations of graphs : A survey, Discrete Mathematics, pp.297-317, 2006.

P. Bibliographie-heggernes, J. A. Telle, and Y. Villanger, Computing minimal triangulations in time O (n? log n)= O (n 2.376 ), Proceedings of the Annual ACM-SIAM symposium on Discrete algorithms, pp.907-916, 2005.

P. Heggernes and Y. Villanger, Efficient implementation of a minimal triangulation algorithm, Proceedings The Annual European Symposium on Algorithms (ESA), pp.175-176, 2002.

M. Held and R. M. Karp, A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, pp.196-210, 1962.

P. V. Hentenryck, Y. Deville, and C. Teng, A generic arc-consistency algorithm and its specializations, Artificial Intelligence, pp.291-321, 1992.

H. H. Hoos and T. Stützle, Stochastic local search : Foundations and applications, 2004.

H. H. Hoos and E. Tsang, Local search methods, Foundations of Artificial Intelligence, pp.135-167, 2006.

J. Huang and A. Darwiche, Using DPLL for efficient OBDD construction, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.157-172, 2004.

B. Hurley, B. O'sullivan, D. Allouche, G. Katsirelos, T. Schiex et al., Multi-language evaluation of exact solvers in graphical model discrete optimization, Constraints, pp.413-434, 2016.

J. Hwang and D. Mitchell,

G. , 2-way vs. d-way branching for CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.343-357, 2005.

P. Janssen, P. Jégou, B. Nouguier, and M. Vilarem, A filtering process for general constraint-satisfaction problems : achieving pairwise-consistency using an associated binary representation, Proceedings of the IEEE Workshop on Tools for Artificial Intelligence, pp.420-427, 1989.

V. Jarnìk, About a certain minimal problem, Práce Moravské Pr?rodovedecké Spolecnosti, pp.57-63, 1930.

P. Jégou, Cyclic-clustering : a compromise between tree-clustering and cycle-cutset method for improving search efficiency, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.369-371, 1990.

P. Jégou, On the consistency of general constraint-satisfaction problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.114-119, 1993.

P. Jégou, H. Kanso, and C. Terrioux, An Algorithmic Framework for Decomposing Constraint Networks, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.1-8, 2015.

P. Jégou, H. Kanso, and C. Terrioux, De nouvelles approches pour la décomposition de réseaux de contraintes, Actes des Journées Francophones de Programmation par Contraintes (JFPC), pp.140-149, 2015.

P. Bibliographie-jégou, H. Kanso, and C. Terrioux, Improving Exact Solution Counting for Decomposition Methods, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.327-334, 2016.

P. Jégou, H. Kanso, and C. Terrioux, Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size, Proceedings of the International Conference on Principle and Practice of Constraint Programming (CP), pp.298-315, 2016.

P. Jégou, H. Kanso, and C. Terrioux, Vers une décomposition dynamique des réseaux de contraintes, Actes des Journées Francophones de Programmation par Contraintes (JFPC), pp.123-132, 2016.

P. Jégou, H. Kanso, and C. Terrioux, Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2017.

P. Jégou, H. Kanso, and C. Terrioux, Vers une exploitation dynamique de la décomposition pour les CSPs pondérés, Actes des Journées Francophones de Programmation par Contraintes (JFPC), 2017.

P. Jégou, S. Ndiaye, and C. Terrioux, Combined strategies for decompositionbased methods for solving CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.184-192, 2009.

P. Jégou, S. N. Ndiaye, and C. Terrioux, Computing and exploiting treedecompositions for solving constraint networks, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.777-781, 2005.

P. Jégou, S. N. Ndiaye, and C. Terrioux, An extension of complexity bounds and dynamic heuristics for tree-decompositions of CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.741-745, 2006.

P. Jégou, S. N. Ndiaye, and C. Terrioux, Strategies and heuristics for exploiting tree-decompositions of constraint networks, Inference methods based on graphical structures of knowledge (WIGSK'06), ECAI workshop, pp.13-18, 2006.

P. Jégou, S. N. Ndiaye, and C. Terrioux, Dynamic Management of Heuristics for Solving Structured CSPs, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.364-378, 2007.

P. Jégou, S. N. Ndiaye, and C. Terrioux, A new Evaluation of Forward Checking and its Consequences on Efficiency of Tools for Decomposition of CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.486-490, 2008.

P. Jégou and C. Terrioux, Hybrid backtracking bounded by tree-decomposition of constraint networks, Artificial Intelligence, pp.43-75, 2003.

P. Jégou and C. Terrioux, A time-space trade-off for constraint networks decomposition, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.234-239, 2004.

P. Bibliographie-jégou and C. Terrioux, Decomposition and good recording for solving Max-CSPs, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.196-200, 2004.

P. Jégou and C. Terrioux, Combining Restarts, Nogoods and Decompositions for Solving CSPs, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.465-470, 2014.

P. Jégou and C. Terrioux, Tree-Decompositions with Connected Clusters for Solving Constraint Networks, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.407-423, 2014.

P. Jégou and C. Terrioux, Combining restarts, nogoods and bag-connected decompositions for solving CSPs, Constraints, pp.191-229, 2017.

F. V. Jensen, S. L. Lauritzen, and K. G. Olesen, Bayesian updating in causal probabilistic networks by local computations, Computational statistics quarterly, pp.269-282, 1990.

J. Jeong, S. Saether, and J. Telle, Maximum matching width : new characterizations and a fast algorithm for dominating set. arXiv, 2015.

B. Jlifi and K. Ghédira, On the enhancement of the informed backtracking algorithm, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.967-967, 2003.

B. Jlifi and K. Ghédira, A Study of Backtracking Based Informed Algorithms, Proceedings of the Starting AI Researchers'Symposium (STAIRS), p.147, 2004.

D. S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the Annual ACM symposium on Theory of computing, pp.38-49, 1973.

M. I. Jordan, Graphical models. Statistical Science, pp.140-155, 2004.

U. Junker, Handbook of constraint programming, pp.837-868, 2006.

N. Jussien, R. Debruyne, and P. Boizumault, Maintaining arc-consistency within dynamic backtracking, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.249-261, 2000.
URL : https://hal.archives-ouvertes.fr/hal-00869126

S. Karakashian, Practical tractability of CSPs by higher level consistency and tree decomposition, 2013.

R. M. Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972.

R. M. Karp and M. Luby, Monte-Carlo algorithms for the planar multiterminal network reliability problem, Journal of Complexity, pp.45-64, 1985.

K. Kask, R. Dechter, and V. Gogate, Counting-based look-ahead schemes for constraint satisfaction, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.317-331, 2004.

G. Bibliographie-katsirelos and F. Bacchus, Unrestricted nogood recording in CSP search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.873-877, 2003.

G. Katsirelos and F. Bacchus, Generalized nogoods in CSPs, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.390-396, 2005.

M. Kitching and F. Bacchus, Exploiting decomposition in constraint optimization problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.478-492, 2008.

U. Kjaerulff, Triangulation of Graphs -Algorithms Giving Small Total State Space, Judex R.R, 1990.

P. G. Kolaitis and M. Y. Vardi, Conjunctive-query containment and constraint satisfaction, Proceedings of the ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp.205-213, 1998.

D. Koller and N. Friedman, Probabilistic graphical models : principles and techniques, 2009.

F. Koriche, J. Lagniez, P. Marquis, T. , and S. , Knowledge Compilation for Model Counting : Affine Decision Trees, SDD : A new canonical representation of propositional knowledge bases, pp.947-953, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00866468

F. Koriche, J. Lagniez, P. Marquis, T. , and S. , Compiling Constraint Networks into Multivalued Decomposable Decision Graphs, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.332-338, 2015.

A. M. Koster, H. L. Bodlaender, and S. P. Hoesel, Treewidth : computational experiments. Electronic Notes in Discrete Mathematics, pp.54-57, 2001.

A. M. Koster, Frequency assignment : Models and algorithms, 1999.

V. Kovalevsky and V. Koval, A diffusion algorithm for decreasing energy of maxsum labeling problem, Glushkov Institute of Cybernetics, 1975.

D. Kratsch and J. Spinrad, Minimal fill in O(n 2.69 ) time. Discrete mathematics, pp.366-371, 2006.

L. Kroc, A. Sabharwal, and B. Selman, Leveraging belief propagation, backtrack search, and statistics for model counting, Proceedings of the International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR), pp.127-141, 2008.

T. K. Kumar, A model counting characterization of diagnoses, 2002.

A. C. Kwan and E. P. Tsang, Minimal forward checking with backmarking and conflict-directed backjumping, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.290-298, 1996.

J. Lagergren, Efficient parallel algorithms for graphs of bounded tree-width, Journal of Algorithms, pp.20-44, 1996.

J. Bibliographie-lagniez and P. Marquis, An Improved Decision-DNNF Compiler, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2017.

J. Lagniez and P. Marquis, On preprocessing techniques and their impact on propositional model counting, Journal of Automated Reasoning, pp.413-481, 2017.

J. Lagniez, P. Marquis, and A. Paparrizou, Defining and Evaluating Heuristics for the Compilation of Constraint Networks, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.172-188, 2017.

A. H. Land and A. G. Doig, An automatic method of solving discrete programming problems, Econometrica : Journal of the Econometric Society, pp.497-520, 1960.

J. Larrosa, Boosting search with variable elimination, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.291-305, 2000.

J. Larrosa, Node and arc consistency in weighted CSP, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.48-53, 2002.

J. Larrosa and R. Dechter, Boosting search with variable elimination in constraint optimization and constraint satisfaction problems, Constraints, pp.303-326, 2003.

J. Larrosa, P. Meseguer, and M. Sánchez, Pseudo-tree search with soft constraints, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.131-135, 2002.

J. Larrosa and T. Schiex, In the quest of the best form of local consistency for weighted CSP, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.239-244, 2003.

J. Larrosa and T. Schiex, Solving weighted CSP by maintaining arc consistency, Artificial Intelligence, pp.1-26, 2004.

S. L. Lauritzen, Graphical models, 1996.

E. L. Lawler and D. E. Wood, Branch-and-bound methods : A survey, Operations research, vol.14, issue.4, pp.699-719, 1966.

C. Lecoutre, STR2 : optimized simple tabular reduction for table constraints, Constraints, pp.341-371, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00868225

C. Lecoutre, Constraint Networks : Targeting Simplicity for Techniques and Algorithms, 2013.

C. Lecoutre, F. Boussemart, and F. Hemery, Exploiting multidirectionality in coarse-grained arc consistency algorithms, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.480-494, 2003.

C. Lecoutre, S. Cardon, and J. Vion, Conservative dual consistency, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.237-242, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00194544

C. Lecoutre, S. Cardon, and J. Vion, Path consistency by dual consistency, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.438-452, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00383830

C. Bibliographie-lecoutre, S. Cardon, and J. Vion, Second-order consistencies, Journal of Artificial Intelligence Research, pp.175-219, 2011.

C. Lecoutre and F. Hemery, A Study of Residual Supports in Arc Consistency, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.125-130, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00261267

C. Lecoutre, C. Likitvivatanavong, and R. H. Yap, STR3 : A path-optimal filtering algorithm for table constraints, Artificial Intelligence, pp.1-27, 2015.

C. Lecoutre, L. Sais, S. Tabary, and V. Vidal, Nogood Recording from Restarts, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.131-136, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00261264

C. Lecoutre, L. Sais, S. Tabary, and V. Vidal, Recording and Minimizing Nogoods from Restarts, Boolean Modeling and Computation (JSAT), pp.147-167, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00191092

C. Lecoutre, L. Saïs, S. Tabary, and V. Vidal, Reasoning from last conflict(s) in constraint programming, Artificial Intelligence, pp.1592-1614, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00868108

C. Lecoutre and R. Szymanek, Generalized arc consistency for positive table constraints, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.284-298, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00121127

C. Lecoutre and J. Vion, Enforcing arc consistency using bitwise operations, Constraint Programming Letters (CPL), pp.21-35, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00868075

J. H. Lee, C. Schulte, and Z. Zhu, Increasing Nogoods in Restart-Based Search, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.3426-3433, 2016.

J. H. Lee and Z. Zhu, An increasing-nogoods global constraint for symmetry breaking during search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.465-480, 2014.

C. Lekkeikerker and J. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, pp.45-64, 1962.

I. Lerman and V. Rouat, Segmentation de la sériation pour la résolution de# SAT, Mathematiques Informatique et Sciences Humaines, pp.113-134, 1999.

O. Lhomme and J. Régin, A fast arc consistency algorithm for n-ary constraints, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.405-410, 2005.

P. Liberatore, On the complexity of choosing the branching literal in DPLL, Artificial intelligence, pp.315-326, 2000.

M. Luby, A. Sinclair, and D. Zuckerman, Optimal speedup of Las Vegas algorithms, Information Processing Letters, pp.173-180, 1993.

I. Lynce, L. Baptista, and J. Silva, Stochastic systematic search algorithms for satisfiability, Electronic Notes in Discrete Mathematics, pp.190-204, 2001.

A. K. Bibliographie-mackworth, Consistency in networks of relations, Artificial intelligence, pp.99-118, 1977.

J. Mairy, P. V. Hentenryck, and Y. Deville, Optimal and efficient filtering algorithms for table constraints, Constraints, pp.77-120, 2014.

M. Mann, G. Tack, W. , and S. , Decomposition during search for propagationbased constraint solvers, 2007.

R. Marinescu and R. Dechter, Advances in and/or branch-and-bound search for constraint optimization, Proceedings of the International Workshop on Preferences and Soft Constraints, 2005.

R. Marinescu and R. Dechter, AND/OR branch-and-bound for graphical models, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.224-229, 2005.

R. Marinescu and R. Dechter, Best-first AND/OR search for graphical models, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.1171-1176, 2007.

H. P. Markowitz, The elimination form of the inverse and its application to linear programming, Management Science, pp.255-269, 1957.

M. Silva, J. P. Lynce, I. , M. , and S. , Conflict-Driven Clause Learning SAT Solvers, pp.131-153, 2009.

D. Mehta and M. Van-dongen, Two new lightweight arc consistency algorithms, Proceedings of the International Workshop on Constraint Propagation and Implementation (CPAI), pp.109-123, 2004.

P. Meseguer and M. Sánchez, Tree-based Russian doll search : Preliminary results, Proceedings of the CP Workshop on Soft Constraints, 2000.

P. Meseguer and M. Sánchez, Specializing russian doll search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.464-478, 2001.

P. Meseguer, M. Sánchez, and G. Verfaillie, Opportunistic specialization in russian doll search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.264-279, 2002.

L. Michel and P. V. Hentenryck, Activity-based search for black-box constraint programming solvers, Proceedings of the International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR), pp.228-243, 2012.

S. Minton, M. D. Johnston, A. B. Philips, L. , and P. , Minimizing conflicts : a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, pp.161-205, 1992.

D. G. Mitchell, Resolution and constraint satisfaction, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.555-569, 2003.

R. Bibliographie-mohr and T. C. Henderson, Arc and path consistency revisited, Artificial intelligence, pp.225-233, 1986.

U. Montanari, Networks of constraints : Fundamental properties and applications to picture processing, Information sciences, pp.95-132, 1974.

M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, M. et al., Chaff : Engineering an efficient SAT solver, Proceedings of the Annual Design Automation Conference, pp.530-535, 2001.

C. J. Muise, S. A. Mcilraith, J. C. Beck, and E. I. Hsu, Dsharp : Fast d-DNNF Compilation with sharpSAT, Proceedings of the Canadian Conference on Artificial Intelligence, pp.356-361, 2012.

M. Müller, Connected tree-width. arXiv, 2012.

B. A. Nadel, Tree search and arc consistency in constraint satisfaction algorithms, Search in artificial intelligence, pp.287-342, 1988.

J. Ne?et?il and P. Mendez, Bounded Height Trees and Tree-Depth. Sparsity, pp.115-144, 2012.

R. Niedermeier, Invitation to fixed-parameter algorithms, 2006.

T. D. Nielsen and F. V. Jensen, Bayesian networks and decision graphs, 2009.

T. Ohtsuki, A fast algorithm for finding an optimal ordering for vertex elimination on a graph, SIAM Journal on Computing, pp.133-145, 1976.

T. Ohtsuki, L. K. Cheung, and T. Fujisawa, Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Journal of Mathematical Analysis and Applications, pp.622-633, 1976.

L. Otten and R. Dechter, Anytime AND/OR depth-first search for combinatorial optimization, AI Communications, pp.211-227, 2012.

S. Oum and P. Seymour, Approximating clique-width and branch-width, Journal of Combinatorial Theory, Series B, pp.514-528, 2006.

U. Oztok and A. Darwiche, On compiling CNF into decision-DNNF, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.42-57, 2014.

H. Palacios, B. Bonet, A. Darwiche, and H. Geffner, Pruning Conformant Plans by Counting Models on Compiled d-DNNF Representations, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp.141-150, 2005.

S. Parter, The use of linear graphs in Gauss elimination, SIAM review, pp.119-130, 1961.

J. Pearl, Heuristics : Intelligent Search Strategies for Computer Problem Solving, 1984.

J. Pearl, Probabilistic reasoning in intelligent systems : Networks of plausible inference, 1988.

J. Pearl, Probabilistic reasoning in intelligent systems : networks of plausible inference, 2014.

J. Pearson and P. G. Jeavons, A survey of tractable constraint satisfaction problems, 1997.

G. Perez and J. Régin, Improving GAC-4 for table and MDD constraints, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.606-621, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01344079

G. Pesant, Counting solutions of CSPs : A structural approach, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.260-265, 2005.

G. Pesant, C. Quimper, and A. Zanarini, Counting-based search : Branching heuristics for constraint satisfaction problems, Journal of Artificial Intelligence Research, 2012.

B. W. Peyton, Minimal orderings revisited. SIAM journal on matrix analysis and applications, pp.271-294, 2001.

C. Pinto and C. Terrioux, A generalized Cyclic-Clustering Approach for Solving Structured CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.724-728, 2009.
URL : https://hal.archives-ouvertes.fr/hal-01488801

K. Pipatsrisawat and A. Darwiche, Width-Based Restart Policies for Clause-Learning Satisfiability Solvers, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.341-355, 2009.

P. Prosser, Hybrid algorithms for the constraint satisfaction problem. Computational intelligence, pp.268-299, 1993.

J. Puget, The next challenge for CP : Ease of use, 2004.

P. Raghavendra and D. Steurer, Graph expansion and the unique games conjecture, Proceedings of the ACM symposium on Theory of computing, pp.755-764, 2010.

B. A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the Annual ACM symposium on Theory of computing, pp.221-228, 1992.

P. Refalo, Impact-based search strategies for constraint programming, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.557-571, 2004.

J. Régin, Generalized arc consistency for global cardinality constraint, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.209-215, 1996.

E. T. Richards and B. Richards, Nogood learning for constraint satisfaction, Proceedings of the CP Workshop on Constraint Programming Applications, 1996.

N. Robertson and P. D. Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, pp.39-61, 1983.

N. Robertson and P. D. Seymour, Graph minors II : Algorithmic aspects of treewidth, Algorithms, pp.309-322, 1986.

N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, Journal of combinatorial theory, Series B, pp.65-110, 1995.

D. J. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph theory and computing, p.217, 1972.

D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on computing, pp.266-283, 1976.

A. Rosenfeld, R. A. Hummel, and S. W. Zucker, Scene labeling by relaxation operations, IEEE Transactions on Systems, Man, and Cybernetics, pp.420-433, 1976.

F. Rossi, P. V. Beek, W. , and T. , Handbook of constraint programming, 2006.

D. Roth, On the hardness of approximate reasoning, Artificial Intelligence, pp.273-302, 1996.

O. Roussel and C. Lecoutre, Xml representation of constraint networks : Format xcsp 2.1. arXiv, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00872825

D. Ruppert, Probabilistic networks and expert systems, 2001.

Z. Ruttkay, Fuzzy constraint satisfaction, Proceedings of the International Conference on Fuzzy Systems, pp.1263-1268, 1994.

V. Ryvchin and O. Strichman, Local restarts in SAT, Constraint Programming Letters (CPL), pp.3-13, 2008.

D. Sabin and E. Freuder, Contradicting Conventional Wisdom in Constraint Satisfaction, Proceedings of European Conference on Artificial Intelligence (ECAI), pp.125-129, 1994.

D. Sabin and E. C. Freuder, Understanding and improving the MAC algorithm, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.167-181, 1997.

M. Samer and S. Szeider, Tractable cases of the extended global cardinality constraint, Constraints, pp.1-24, 2011.

M. Samer and H. Veith, Encoding treewidth into SAT, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.45-50, 2009.

M. Sanchez, D. Allouche, S. D. Givry, and T. Schiex, Russian Doll Search with Tree Decomposition, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.603-608, 2009.

T. Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial intelligence, pp.1-54, 2002.

T. Sang, F. Bacchus, P. Beame, H. A. Kautz, and T. Pitassi, Combining Component Caching and Clause Learning for Effective Model Counting, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), 2004.

T. Sang, P. Beame, and H. A. Kautz, Performing Bayesian inference by weighted model counting, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.475-481, 2005.

T. Schiex, Possibilistic constraint satisfaction problems or how to handle soft constraints ?, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.268-275, 1992.

T. Schiex, Arc consistency for soft constraints, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.411-425, 2000.

T. Schiex, H. Fargier, and G. Verfaillie, Valued constraint satisfaction problems : Hard and easy problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.631-639, 1995.

T. Schiex and G. Verfaillie, Two approaches to the solution maintenance problem in dynamic constraint satisfaction problems, Proceedings of the IJCAI Workshop on Knowledge-based Production Planning, Scheduling and Control, 1993.

T. Schiex and G. Verfaillie, Nogood recording for static and dynamic constraint satisfaction problems, International Journal on Artificial Intelligence Tools, pp.187-207, 1994.

T. Schiex and G. Verfaillie, Stubborness : A Possible Enhancement for Backjumping and Nogood Recording, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.165-172, 1994.

P. Seymour and R. Thomas, Call routing and the ratcatcher, Combinatorica, pp.217-241, 1994.

R. D. Shachter, S. K. Andersen, and P. Szolovits, Global conditioning for probabilistic inference in belief networks, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.514-522, 1994.

G. R. Shafer and P. P. Shenoy, Probability propagation, Annals of Mathematics and Artificial Intelligence, pp.327-351, 1990.

K. Shoikhet and D. Geiger, A practical algorithm for finding optimal triangulations, Proceedings of the National Conference on Artificial Intelligence (AAAI) and of the Conference on Innovative Applications of Artificial Intelligence (IAAI), pp.185-190, 1997.

F. Slivovsky and S. Szeider, Model counting for formulas of bounded clique-width, International Symposium on Algorithms and Computation (ISAAC), pp.677-687, 2013.

B. Smith, The Brélaz heuristic and optimal static orderings, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.405-418, 1999.

B. M. Smith, The phase transition and the mushy region in constraint satisfaction problems, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.100-104, 1994.

B. M. Smith and P. Sturdy, Value ordering for finding all solutions, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.311-316, 2005.

R. M. Bibliographie-stallman and G. J. Sussman, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artificial intelligence, pp.135-196, 1977.

S. Subbarayan, L. Bordeaux, and Y. Hamadi, Knowledge compilation properties of tree-of-BDDs, Proceedings of the National Conference on Artificial Intelligence (AAAI), p.502, 2007.

R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on computing, pp.566-579, 1984.

C. Terrioux and P. Jégou, Bounded backtracking for the valued constraint satisfaction problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.709-723, 2003.

M. Thurley, sharpSAT-counting models with advanced component caching and implicit BCP, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.424-429, 2006.

S. Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, pp.865-877, 1991.

J. R. Ullmann, Associating parts of patterns, Information and Control, pp.583-601, 1966.

J. R. Ullmann, An algorithm for subgraph isomorphism, Journal of the ACM (JACM), pp.31-42, 1976.

J. R. Ullmann, Partition search for non-binary constraint satisfaction, Information Sciences, pp.3639-3678, 2007.

L. G. Valiant, The complexity of computing the permanent, Theoretical computer science, pp.189-201, 1979.

W. Van-hoeve and I. Katriel, Handbook of constraint programming, pp.245-280, 2006.

G. Verfaillie, Problemes de satisfaction de contraintes : production et révision de solution par modifications locales, Proceedings of the International Avignon Workshop, pp.277-286, 1993.

G. Verfaillie, M. Lemaître, and T. Schiex, Russian doll search for solving constraint optimization problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.181-187, 1996.

Y. Villanger, Improved exponential-time algorithms for treewidth and minimum fill-in, Proceedings of the Latin American Theoritical Informatics Symposium (LA-TIN), pp.800-811, 2006.

T. Walsh, Search in a small world, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.1172-1177, 1999.

T. Walsh, SAT v CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.441-456, 2000.

D. L. Waltz, Generating Semantic Descriptions From Drawings of Scenes With Shadows, 1972.

R. Wang, W. Xia, R. H. Yap, and Z. Li, Optimizing Simple Tabular Reduction with a Bitwise Representation, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.787-795, 2016.

W. Wei and B. Selman, A new approach to model counting, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.324-339, 2005.

P. Wollan, The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, pp.47-66, 2015.

M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM Journal on Algebraic Discrete Methods, pp.77-79, 1981.

Y. Zhang and R. H. Yap, Making AC-3 an optimal algorithm, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.316-321, 2001.