]. S. Références1, D. G. Arnborg, A. Corneil, and . Proskurowski, Complexity of finding embeddings in a k-tree, SIAM. J. on Algebraic and Discrete Methods, vol.8, pp.277-284, 1987.

E. Bensana, M. Lema??trelema??tre, and G. Verfaillie, Earth observation satellite management, Constraints, vol.4, issue.3, pp.293-299, 1999.
DOI : 10.1023/A:1026488509554

B. Cabon, S. De-givry, L. Lobjois, T. Schiex, and J. P. Warners, Radio link frequency assignment, Constraints, vol.4, issue.1, pp.79-89, 1999.
DOI : 10.1023/A:1009812409930

M. Fontaine, S. Loudni, and P. Boizumault, Guiding VNS with Tree Decomposition, 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence, pp.505-512, 2011.
DOI : 10.1109/ICTAI.2011.82
URL : https://hal.archives-ouvertes.fr/hal-01018444

P. Hansen, N. Mladenovic, and D. Perez-brito, Variable neighborhood decomposition search, Journal of Heuristics, vol.7, issue.4, pp.335-350, 2001.
DOI : 10.1023/A:1011336210885

W. D. Harvey and M. L. Ginsberg, Limited discrepancy search, IJCAI'95, pp.607-615, 1995.

P. Jégou, S. Ndiaye, and C. Terrioux, Computing and Exploiting Tree-Decompositions for Solving Constraint Networks, CP, pp.777-781, 2005.
DOI : 10.1007/11564751_63

M. Kitching and F. Bacchus, Exploiting decomposition on constraint problems with high tree-width, IJCAI, pp.525-531, 2009.

J. Larrosa and T. Schiex, In the quest of the best form of local consistency for weighted CSP, IJCAI, pp.239-244, 2003.

S. Loudni and P. Boizumault, Combining VNS with constraint programming for solving anytime optimization problems, European Journal of Operational Research, vol.191, issue.3, pp.705-735, 2008.
DOI : 10.1016/j.ejor.2006.12.062

R. Marinescu and R. Dechter, AND/OR Branch-and-Bound search for combinatorial optimization in graphical models, Artificial Intelligence, vol.173, issue.16-17, pp.16-171457, 2009.
DOI : 10.1016/j.artint.2009.07.003

N. Mladenovic and P. Hansen, Variable neighborhood search, Computers & Operations Research, vol.24, issue.11, pp.1097-1100, 1997.
DOI : 10.1016/S0305-0548(97)00031-2
URL : https://hal.archives-ouvertes.fr/hal-00979295

B. Neveu and G. Trombettoni, INCOP: An Open Library for INcomplete Combinatorial OPtimization, Principles and Practice of Constraint Programming?CP 2003, pp.909-913, 2003.
DOI : 10.1007/978-3-540-45193-8_77

B. Neveu, G. Trombettoni, and F. Glover, ID Walk: A Candidate List Strategy with a Simple Diversification Device, CP'04, pp.423-437, 2004.
DOI : 10.1007/978-3-540-30201-8_32

L. Perron, P. Shaw, and V. Furnon, Propagation guided large neighborhood search. Principles and Practice of Constraint Programming?CP, pp.468-481, 2004.
DOI : 10.1007/978-3-540-30201-8_35

N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3, pp.309-322, 1986.
DOI : 10.1016/0196-6774(86)90023-4
URL : http://doi.org/10.1006/jctb.1999.1919

M. Sánchez, D. Allouche, S. De-givry, and T. Schiex, Russian doll search with tree decomposition, IJCAI, pp.603-608, 2009.

P. Shaw, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, CP-98
DOI : 10.1007/3-540-49481-2_30

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, vol.13, issue.3, pp.566-579, 1984.
DOI : 10.1137/0213035