J. Bibliographie-[-abfkn02-]-alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier, Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, vol.33, pp.461-493, 2002.

J. Alber and R. Niedermeier, Improved Tree Decomposition Based Algorithms for Domination-like Problems, Proceedings of LATIN 2002, pp.221-233, 2002.
DOI : 10.1007/3-540-45995-2_52

J. A. And03-]-anderson, Discrete Mathematics with Combinatorics. 2 e édition, pp.31-54, 2003.

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol.12, issue.2, pp.308-340, 1991.
DOI : 10.1016/0196-6774(91)90006-K

URL : http://www.aifb.uni-karlsruhe.de/CoM/seese/publications/../../publications/tree-decomposable_graphs.pdf

S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, vol.23, issue.1, pp.11-24, 1989.
DOI : 10.1016/0166-218X(89)90031-0

URL : https://doi.org/10.1016/0166-218x(89)90031-0

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-spaccamela et al., Complexity and approximation : combinatorial optimization problems and their approximability properties, p.25, 1999.
DOI : 10.1007/978-3-642-58412-1

R. Beigel, Finding maximum independent sets in sparse and general graphs, Proceedings of SODA 1999, pp.856-857

R. Beigel and D. , 3-coloring in time, Journal of Algorithms, vol.54, issue.2, pp.168-204, 2005.
DOI : 10.1016/j.jalgor.2004.06.008

A. Berry, J. P. Bordat, and O. Cogis, GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH, International Journal of Foundations of Computer Science, vol.855, issue.03, pp.397-403, 2000.
DOI : 10.1016/S0304-3975(97)83809-1

A. A. Bertossi, Dominating sets for split and bipartite graphs, Information Processing Letters, vol.19, issue.1, pp.37-40, 1984.
DOI : 10.1016/0020-0190(84)90126-1

A. Björklund and T. Husfeldt, Inclusion--Exclusion Algorithms for Counting Set Partitions, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.575-582
DOI : 10.1109/FOCS.2006.41

A. Björklund, T. Husfeldt, and M. Koivisto, Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, p.55
DOI : 10.1137/070683933

J. R. Blair and B. W. Peyton, An introduction to chordal graphs and clique trees, Graph theory and sparse matrix computation, The IMA Volumes in Mathematics and its Applications 56, pp.1-29, 1993.

H. L. Bodlaender, A tourist guide through treewidth, Acta Cybernetica, vol.11, pp.1-23, 1993.

H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, vol.209, issue.1-2, pp.1-45, 1998.
DOI : 10.1016/S0304-3975(97)00228-4

H. L. Bodlaender, Discovering Treewidth, technical report UU-CS-2005-018, institute of information and computing sciences, p.72

H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree, Journal of Algorithms, vol.18, issue.2, pp.238-255, 1995.
DOI : 10.1006/jagm.1995.1009

H. L. Bodlaender and R. H. Möhring, The Pathwidth and Treewidth of Cographs, SIAM Journal on Discrete Mathematics, vol.6, issue.2, pp.181-188, 1993.
DOI : 10.1137/0406014

K. S. Booth and J. H. Johnson, Dominating Sets in Chordal Graphs, SIAM Journal on Computing, vol.11, issue.1, pp.191-199, 1982.
DOI : 10.1137/0211015

R. Boppana and M. M. Halldórsson, Approximating Maximum Independent Sets by Excluding Subgraphs, Proceedings of SWAT 1990, pp.13-25, 1990.
DOI : 10.1007/bf01994876

URL : http://www.cs.umd.edu/~gasarch/ramsey/indset.ps

V. Bouchitté and I. Todinca, Treewidth and Minimum Fill-in: Grouping the Minimal Separators, SIAM Journal on Computing, vol.31, issue.1, pp.212-232, 2001.
DOI : 10.1137/S0097539799359683

A. Brandstädt and D. Kratsch, On domination problems for permutation and other graphs, Theoretical Computer Science, vol.54, issue.2-3, pp.181-198, 1987.
DOI : 10.1016/0304-3975(87)90128-9

A. Brandstädt, V. B. Le, and J. Spinrad, Graph Classes : A Survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM, vol.19, issue.21, pp.17-80, 1999.
DOI : 10.1137/1.9780898719796

T. Brueggemann and W. Kern, An improved local search algorithm for 3-SAT, Electronic Notes in Discrete Mathematics, vol.17, pp.303-313, 2004.
DOI : 10.1016/j.endm.2004.03.021

N. H. Bshouty and L. Burroughs, Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem, Proceedings of STACS 1998, pp.298-308, 1998.
DOI : 10.1007/BFb0028569

J. M. Byskov, Enumerating maximal independent sets with applications to graph colouring, Operations Research Letters, vol.32, issue.6, pp.547-556, 2004.
DOI : 10.1016/j.orl.2004.03.002

J. M. Byskov, B. A. Madsen, and B. Skjernaa, On the number of maximal bipartite subgraphs of a graph, Journal of Graph Theory, vol.6, issue.2, pp.127-132, 2005.
DOI : 10.7155/jgaa.00064

L. Cai, Parameterized complexity of cardinality constrained optimization problems , manuscrit, mai, p.144, 2005.

P. J. Cameron, Combinatorics : Topics, Techniques, Algorithms, pp.31-45, 1994.

L. S. Chandran and F. Grandoni, Refined memorization for vertex cover, Information Processing Letters, vol.93, issue.3, pp.125-131, 2005.
DOI : 10.1016/j.ipl.2004.10.003

M. S. Chang, Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs, SIAM Journal on Computing, vol.27, issue.6, pp.1671-1694, 1998.
DOI : 10.1137/S0097539792238431

J. Chen, I. A. Kanj, and G. Xia, Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems, Algorithmica, vol.43, issue.4, pp.245-273, 2005.
DOI : 10.1007/s00453-004-1145-7

M. Chlebík and J. Chlebíková, Approximation Hardness of Dominating Set Problems, Proceedings of ESA 2004, pp.192-203, 2004.
DOI : 10.1007/978-3-540-30140-0_19

E. J. Cockayne, P. A. Jr, S. M. Dreyer, S. T. Hedetniemi, and . Hedetniemi, Roman domination in graphs, Discrete Mathematics, vol.278, issue.1-3, pp.11-22, 2004.
DOI : 10.1016/j.disc.2003.06.004

URL : https://doi.org/10.1016/j.disc.2003.06.004

S. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing , STOC '71, pp.151-158
DOI : 10.1145/800157.805047

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction à l'algorithmique. 2 e édition. Dunod, pp.12-45, 2002.

M. B. Cozzens and L. L. Kelleher, Dominating cliques in graphs, Discrete Mathematics, vol.86, issue.1-3, pp.101-116, 1990.
DOI : 10.1016/0012-365X(90)90353-J

URL : https://doi.org/10.1016/0012-365x(90)90353-j

J. Culberson, Y. Gao, and C. Anton, Phase Transitions of Dominating Clique Problem and Their Implications to Satisfiability Search, Proceedings of IJCAI 2005, pp.78-83

V. Dah06-]-dahlöf, Exact algorithms for exact satisfiability problems, p.137, 2006.

V. Dahlöf, P. Jonsson, and R. Beigel, Algorithms for four variants of the exact satisfiability problem, Theoretical Computer Science, vol.320, issue.2-3, pp.373-394, 2004.
DOI : 10.1016/j.tcs.2004.02.035

M. Davis, G. Logemann, and D. Loveland, A machine program for theorem-proving, Communications of the ACM, vol.5, issue.7, pp.394-397, 1962.
DOI : 10.1145/368273.368557

M. Davis and H. Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM, vol.7, issue.3, pp.201-215, 1960.
DOI : 10.1145/321033.321034

F. Dehne, M. R. Fellows, H. Fernau, E. Prieto, and F. , nonblocker: Parameterized Algorithmics for minimum dominating set, Proceedings of SOFSEM 2006, pp.237-245, 2006.
DOI : 10.1007/11611257_21

URL : http://www.dehne.carleton.ca/publications/pdf/2-79.pdf

E. W. Dij59-]-dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol.4, issue.1, pp.269-271, 1959.
DOI : 10.1007/BF01386390

F. Dor07a-]-dorn, How to use planarity efficiently : new tree-decomposition based algorithms , à paraître dans proceedings of WG, p.70, 2007.

F. Dorn, Designing Subexponential Algorithms : Problems, Techniques & Structures, p.70, 2007.

R. G. Downey and M. R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, vol.24, issue.4, pp.873-921, 1995.
DOI : 10.1137/S0097539792228228

URL : http://homepages.ecs.vuw.ac.nz/~downey/publications/1.pdf

. Df95b, R. G. Downey, and M. R. Fellows, Fixed-parameter tractability and completeness II : On completeness for W [1], Theoretical Computer Science, vol.141, pp.109-131, 1995.

R. G. Downey and M. R. Fellows, Parameterized complexity, pp.35-58, 1999.
DOI : 10.1007/978-1-4612-0515-9

J. E. Dunbar, D. J. Erwin, T. W. Haynes, S. M. Hedetniemi, and S. T. Hedetniemi, Broadcasts in graphs, Discrete Applied Mathematics, vol.154, issue.1, pp.59-75, 2006.
DOI : 10.1016/j.dam.2005.07.009

D. Eppstein, Small Maximal Independent Sets and Faster Exact Graph Coloring, Journal of Graph Algorithms and Applications, vol.7, issue.2, pp.131-140, 2003.
DOI : 10.7155/jgaa.00064

URL : http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf

D. Eppstein, Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms, ACM Transactions on Algorithms, vol.2, issue.4, pp.492-509, 2006.
DOI : 10.1145/1198513.1198515

D. Eppstein, The Traveling Salesman Problem for Cubic Graphs, Journal of Graph Algorithms and Applications, vol.11, issue.1, pp.61-81, 2007.
DOI : 10.7155/jgaa.00137

URL : http://arxiv.org/pdf/cs/0302030v2.pdf

D. J. Erwin, Dominating broadcasts in graphs, Bulletin of the Institute of Combinatorics and its Applications, pp.89-105, 2004.

L. Euler, Solutio problematis ad geometriam situs pertinentis, Opera Omnia, vol.7, issue.2, pp.128-140, 1736.

M. Farber, Domination in permutation graphs, Journal of Algorithms, vol.6, issue.3, pp.309-321, 1985.
DOI : 10.1016/0196-6774(85)90001-X

U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM, vol.45, issue.4, pp.634-652, 1998.
DOI : 10.1145/285055.285059

U. Feige, Coping with the NP-Hardness of the Graph Bandwidth Problem, Proceedings of SWAT 2000, pp.129-145, 2000.
DOI : 10.1007/3-540-44985-X_2

R. Sedgewick and P. Flajolet, Introduction à l'analyse des algorithmes, p.45, 1998.

F. V. Fomin, D. Kratsch, and G. J. Woeginger, Exact (Exponential) Algorithms for the Dominating Set Problem, Proceedings of WG 2004, pp.245-256, 2004.
DOI : 10.1007/978-3-540-30559-0_21

F. V. Fomin, S. Gaspers, and A. V. Pyatkin, Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$, Proceedings of IWPEC 2006, pp.184-191, 2006.
DOI : 10.1007/11847250_17

F. V. Fomin, P. A. Golovach, J. Kratochvíl, D. Kratsch, and M. Liedloff, Branch and Recharge : Exact Algorithms for Generalized Domination, Proceedings of WADS 2007, pp.508-519, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00460736

F. V. Fgk05a-]-fomin, F. Grandoni, and D. Kratsch, Measure and conquer : Domination -A case study, Proceedings of ICALP 2005, pp.192-203, 2006.

F. V. Fomin, F. Grandoni, and D. Kratsch, Some new techniques in design and analysis of exact (exponential) algorithms, Bulletin of the EATCS, vol.87, pp.47-77, 2005.

F. V. Fgk06a-]-fomin, F. Grandoni, and D. Kratsch, Measure and conquer : A simple O(2 0.288n ) independent set algorithm, Proceedings of SODA 2006, pp.18-25, 2006.

F. V. Fomin, F. Grandoni, and D. Kratsch, Solving Connected Dominating Set Faster than 2 n, Proceedings of FSTTCS 2006, pp.152-163, 2006.

F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov, Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach, Proceedings of ISAAC 2005, pp.573-582, 2006.
DOI : 10.1007/11602613_58

F. V. Fomin and K. Høie, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters, vol.97, issue.5, pp.191-196, 2006.
DOI : 10.1016/j.ipl.2005.10.012

F. V. Fomin and A. A. Stepanov, Counting Minimum Weighted Dominating Sets, Proceedings of COCOON 2007, p.67
DOI : 10.1007/978-3-540-73545-8_18

D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, vol.15, issue.3, pp.835-855, 1965.
DOI : 10.2140/pjm.1965.15.835

M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Company, pp.16-57, 1979.

W. Gasarch, Guest Column, ACM SIGACT News, vol.43, issue.2, 2002.
DOI : 10.1145/2261417.2261434

S. Gaspers, D. Kratsch, and M. Liedloff, Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes, Proceedings of SWAT 2006, pp.148-159, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00460694

S. Gaspers, D. Kratsch, M. Liedloff, and I. Todinca, Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes, article sousmis à ACM Transactions on Algorithms, p.6

S. Gaspers and M. Liedloff, A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs, Proceedings of WG 2006, pp.78-89, 2006.
DOI : 10.1007/11917496_8

URL : https://hal.archives-ouvertes.fr/hal-00460733

S. Gaspers and M. Liedloff, A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs, p.95, 2007.
DOI : 10.1007/11917496_8

URL : https://hal.archives-ouvertes.fr/hal-00460733

F. Gavril, Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph, SIAM Journal on Computing, vol.1, issue.2, pp.180-187, 1972.
DOI : 10.1137/0201013

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, pp.16-79, 1980.

T. F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, vol.38, pp.293-306, 1985.
DOI : 10.1016/0304-3975(85)90224-5

R. L. Graham, D. E. Knuth, and O. Patashnik, Mathématiques concrètes : Fondations pour l'informatique. Vuibert, p.31, 2003.

F. Grandoni, Exact Algorithms for Hard Graph Problems, p.61, 2004.

F. Grandoni, A note on the complexity of minimum dominating set, Journal of Discrete Algorithms, vol.4, issue.2, pp.209-214, 2006.
DOI : 10.1016/j.jda.2005.03.002

R. Greenlaw and R. Petreschi, Cubic graphs, ACM Computing Surveys, vol.27, issue.4, pp.471-495, 1995.
DOI : 10.1145/234782.234783

J. Guo, R. Niedermeier, and S. Wernicke, Parameterized complexity of vertex cover variants, à paraître dans Theory of Computing Systems, p.144

S. Gupta, V. Raman, and S. Saurabh, Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems, Proceedings of FSTTCS 2006, pp.139-151, 2006.
DOI : 10.1007/11944836_15

. Hhs98a, T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, pp.3-60, 1998.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs, pp.3-60, 1998.
DOI : 10.1201/b16132-65

R. Hayward and H. , Meyniel weakly triangulated graphs ??? I: Co-perfect orderability, Discrete Applied Mathematics, vol.73, issue.3, pp.199-210, 1997.
DOI : 10.1016/S0166-218X(96)00008-X

URL : https://doi.org/10.1016/s0166-218x(96)00008-x

P. Heg06-]-heggernes, Minimal triangulations of graphs: A survey, Discrete Mathematics, vol.306, issue.3, pp.297-317, 2006.
DOI : 10.1016/j.disc.2005.12.003

P. Heggernes and D. Lokshtanov, Optimal broadcast domination in polynomial time, Discrete Mathematics, vol.306, issue.24, pp.3267-3280, 2006.
DOI : 10.1016/j.disc.2006.06.013

M. Held and R. M. Karp, A dynamic programming approach to sequencing problems, Journal of SIAM, vol.4, issue.38, pp.196-210, 1962.
DOI : 10.1137/0110015

D. S. Hochbaum and D. B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM, vol.33, issue.3, pp.533-550, 1986.
DOI : 10.1145/5925.5933

E. Horowitz and S. Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM, vol.21, issue.2, pp.277-292, 1974.
DOI : 10.1145/321812.321823

URL : http://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf

S. B. Horton, C. N. Meneses, A. Mukherjee, and M. E. Uluçakli, A computational study of the broadcast domination problem, DIMACS Center for Discrete Mathematics and Theoretical Computer Science, pp.277-292, 2004.

W. L. Hsu and G. L. Nemhauser, Easy and hard bottleneck location problems, Discrete Applied Mathematics, vol.1, issue.3, pp.209-216, 1979.
DOI : 10.1016/0166-218X(79)90044-1

URL : https://doi.org/10.1016/0166-218x(79)90044-1

W. L. Hsu and K. H. Tsai, Linear time algorithms on circular-arc graphs, Information Processing Letters, vol.40, issue.3, pp.123-129, 1991.
DOI : 10.1016/0020-0190(91)90165-E

D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, pp.1098-1101, 1952.

R. Impagliazzo, R. Paturi, and F. Zane, Which Problems Have Strongly Exponential Complexity?, Journal of Computer and System Sciences, vol.63, issue.4, pp.512-530, 2001.
DOI : 10.1006/jcss.2001.1774

URL : https://doi.org/10.1006/jcss.2001.1774

K. Iwama, Worst-case upper bounds for kSAT, Bulletin of the EATCS, vol.82, pp.61-71, 2004.

T. Jian and O. An, 0.304n ) algorithm for solving maximum independent set problem, IEEE Trans. Computers, vol.35, issue.2, pp.847-851, 1986.

D. S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, vol.9, issue.3, pp.256-278, 1974.
DOI : 10.1016/S0022-0000(74)80044-9

URL : https://doi.org/10.1016/s0022-0000(74)80044-9

D. S. Johnson, The NP-completeness column: An ongoing guide, Journal of Algorithms, vol.8, issue.2, pp.285-303, 1987.
DOI : 10.1016/0196-6774(87)90043-5

URL : http://www.research.att.com/~dsj/columns/col19.pdf

D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, vol.27, issue.3, pp.119-123, 1988.
DOI : 10.1016/0020-0190(88)90065-8

R. M. Karp, Dynamic programming meets the principle of inclusion and exclusion, Operations Research Letters, vol.1, issue.2, pp.49-51, 1982.
DOI : 10.1016/0167-6377(82)90044-X

J. M. Kei93-]-keil, The complexity of domination problems in circle graphs, Discrete Applied Mathematics, vol.42, issue.1, pp.51-63, 1993.
DOI : 10.1016/0166-218X(93)90178-Q

T. Kloks and D. Kratsch, Listing all Minimal Separators of a Graph, SIAM Journal on Computing, vol.27, issue.3, pp.605-613, 1998.
DOI : 10.1137/S009753979427087X

D. E. Knuth, The Art of Computer Programming Sorting and Searching, pp.42-53, 1997.

J. Kratochvíl, D. Kratsch, and M. Liedloff, Exact Algorithms for L(2,1)-Labeling of Graphs, Proceedings of MFCS 2007, pp.513-524, 2007.
DOI : 10.1007/978-3-540-74456-6_46

D. Kratsch, T. Haynes, S. Hedetniemi, and P. Slater, Algorithms, Domination in Graphs : Advanced Topics Marcel Dekker, pp.191-231, 1998.
URL : https://hal.archives-ouvertes.fr/hal-00460774

D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics, vol.99, issue.1-3, pp.111-123, 2000.
DOI : 10.1016/S0166-218X(99)00128-6

URL : https://doi.org/10.1016/s0166-218x(99)00128-6

D. Kratsch, Communication personnelle, p.67, 2005.

D. Kratsch, P. Damaschke, and A. Lubiw, Dominating cliques in chordal graphs, Discrete Mathematics, vol.128, issue.1-3, pp.269-275, 1994.
DOI : 10.1016/0012-365X(94)90118-X

D. Kratsch and M. Liedloff, An Exact Algorithm for the Minimum Dominating Clique Problem, Proceedings of IWPEC 2006, pp.130-141, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00460727

D. Kratsch and M. Liedloff, An Exact Algorithm for the Minimum Dominating Clique Problem, à paraître dans Theoretical Computer Science, p.7

D. Kratsch and L. Stewart, Domination on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.3, pp.400-417, 1993.
DOI : 10.1137/0406032

J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, vol.7, issue.1, pp.48-50, 1956.
DOI : 10.1090/S0002-9939-1956-0078686-7

O. Kullmann and H. Luckhardt, Algorithms for SAT/TAUT decision based on various measures, manuscrit, février 1999, p.45

E. L. Lawler, A note on the complexity of the chromatic number problem, Information Processing Letters, vol.5, issue.3, pp.66-67, 1976.
DOI : 10.1016/0020-0190(76)90065-X

É. Dea-informatique-de-lorraine, Domination Romaine Laboratoire d'Informatique Théorique et Appliquée de l'Université Paul Verlaine -Metz, juin, Proceedings of WG 2005, pp.145-103, 2004.

W. Mccuaig and B. Shepherd, Domination in graphs with minimum degree two, Journal of Graph Theory, vol.9, issue.6, pp.749-762, 1989.
DOI : 10.1090/coll/038

S. Micali and V. V. Vazirani, An O( |V ||E|) Algorithm for Finding Maximum Matching in General Graphs, Proceedings of FOCS 1980, pp.17-27

J. W. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics, vol.3, issue.1, pp.23-28, 1965.
DOI : 10.1007/BF02760024

R. Motwani and P. Raghavan, Randomized Algorithms, p.25, 1995.

R. Nie06-]-niedermeier, Invitation to Fixed Parameter Algorithms, pp.26-80, 2006.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

R. Niedermeier and P. Rossmanith, On efficient fixed-parameter algorithms for weighted vertex cover, Journal of Algorithms, vol.47, issue.2, pp.63-77, 2003.
DOI : 10.1016/S0196-6774(03)00005-1

. Pap94, C. H. Papadimitriou, A. Pagourtzis, P. Penna, K. Schlude et al., Computational Complexity Server Placements, Roman Domination and other Dominating Set Variants, Proceedings of IFIP International Conference on Theoretical Computer Science : Foundations of Information Technology in the Era of Networking and Mobile Computing, pp.280-291, 1994.

P. A. Peterson and M. C. Loui, The general maximum matching algorithm of micali and vazirani, Algorithmica, vol.22, issue.1-4, pp.511-533, 1988.
DOI : 10.1137/1.9781611970265

J. Ple80-]-plesník, On the computational complexity of centers locating in a graph, Aplikace Matematiky, vol.25, pp.445-452, 1980.

W. H. Press, B. P. Flannery, and S. A. Teukolsky, Numerical Recipes in C : The Art of Scientific Computing. 2 e édition, p.45, 1992.

. Pri57 and R. C. Prim, Shortest connection networks and some generalisations, Bell System Technical Journal, vol.36, pp.1389-1401, 1957.

B. Randerath and I. Schiermeyer, Exact algorithms for Minimum Dominating Set, pp.61-98, 2004.

R. Raz and S. Safra, A sub-constant error-probability low-degree test, and subconstant error-probability PCP characterization of NP, Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp.475-484, 1997.

I. Raz06a-]-razgon, Exact Computation of Maximum Induced Forest, Proceedings of SWAT 2006, pp.160-171, 2006.
DOI : 10.1007/11785293_17

I. Razgon, A Faster Solving of the Maximum Independent Set Problem for Graphs with Maximal Degree 3, Proceedings of the Second ACiD Workshop, pp.131-142, 2006.

J. Riordan, N. Robertson, and P. D. Seymour, An Introduction to Combinatorial Analysis Graph Minors. II. Algorithmic Aspects of Tree- Width, Journal of Algorithms, vol.54, issue.7, pp.31-309, 1958.

J. M. Robson, Algorithms for maximum independent sets, Journal of Algorithms, vol.7, issue.3, pp.425-440, 1986.
DOI : 10.1016/0196-6774(86)90032-5

J. M. Robson and J. Van-rooij, Finding a maximum independent set in time O Design by Measure and Conquer : An O(1.5086 n ) algorithm for minimum dominating set and similar problems, pp.40-69, 2001.

K. H. Rosen, Discrete Mathematics and Its Applications. 6 e édition, pp.31-54, 2006.

I. Schiermeyer, Problems remaining NP-complette for sparse or dense graphs, Discussiones Mathematicae Graph Theory, vol.15, issue.1, pp.33-41, 1995.
DOI : 10.7151/dmgt.1004

M. Schnupp, Broadcast Domination with flexible powers, p.162, 2006.

U. Schöning, Algorithmics in Exponential Time, Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), pp.36-43, 2005.
DOI : 10.1007/978-3-540-31856-9_3

R. Schroeppel, A. Shamir, and A. T. , n/4 ) algorithm for certain NP-complete problems, SIAM Journal on Computing, vol.3, issue.136, pp.456-464, 1981.

M. I. Shamos and D. Hoey, Closest-point problems, 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pp.151-162
DOI : 10.1109/SFCS.1975.8

M. Shindo and E. Tomita, Simple algorithms for finding a maximum clique and its worst case time complexity, Systems and computers in Japan 21, pp.1-13, 1990.

. Spi03 and J. P. Spinrad, Efficient Graph Representation, Fields Institute Monographs, p.80, 2003.

J. A. Telle, Complexity of domination-type problems in graphs, Nordic Journal of Computing, vol.1, issue.59, pp.157-171, 1994.

R. E. Tarjan, A. E. Trojanowski-vazirani, and V. V. , Finding a Maximum Independent Set, Proceedings of LATIN 2006, pp.537-546, 1977.
DOI : 10.1137/0206038

D. West, Introduction to Graph Theory, p.16, 1996.

R. Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical Computer Science, vol.348, issue.2-3, pp.357-365, 2005.
DOI : 10.1016/j.tcs.2005.09.023

G. J. Woeginger, Exact algorithms for NP-hard problems : A survey, Combinatorial Optimization -Eureka, You Shrink !, LNCS, vol.2570, issue.38, pp.185-207, 2003.

G. J. Woeginger, Space and Time Complexity of Exact Algorithms: Some Open Problems, Proceedings of the 1st International Workshop on Parameterized and Exact Computation, pp.281-290, 2004.
DOI : 10.1007/978-3-540-28639-4_25

T. Yato and T. Seta, Complexity and completeness of finding another solution and its application to puzzles, Proceedings of the National Meeting of the, 2002.