S. and F. Donc-y-?-d-\-s,

.. Si-v-=-x,-alors-v-h-y-?-e(g)-pour-tout-h-?-{-j, k}, car v j < x ? r x ? r v j et

W. Puisque, .. .. {1, and .. {1, j ? 1} tel que < h, mais cela contredit le choix de x et j . Par conséquent, D est irredondant ; contradiction. Maintenant, on affirme que les sommets de N H

. S&apos;il-existe-un-sommet-x-?-n-h, ] qui est un privé pour un sommet v ? D \ (S ? {w}), alors xw ? E(G) et, par conséquent, r v < w . Cela implique que v ? N H [v i ] et v = w se contredisent N H

S. Soit, F. =-s-?{w}, X. F\n-h-[v-i-], F. X\n-h-;-s, and X. Régulier, On note que si y ? F ?X , alors y > r v i et w ? r v i < y ? r y et, par conséquent

S. , F. , X. , F. , X. )-tel-que et al., Aussi, c'est facile de voir que les étapes de l'algorithme sont exhaustives. Donc l'algorithme s'arrête toujours. Afin d'énumérer tous les ensembles irredondants maximaux dans un graphe d'intervalles G, il suffit d'appeler ENUMIS-I( , V(G)). L'algorithme génère des ensembles seulement à l'étape 1 et il affiche, après une vérification en temps polynomial, un ensemble s'il est uniquement un ensemble irredondant maximal

F. |x-|-+-|f-|-&lt;-|x|-+-|f|-;-s and X. ). , On montre, par récurrence sur |X| + |F|, que si D est compatible avec un triplet régulier (S, F, X) des sous-ensembles disjoints de V(G), alors ENUMIS-I(S, F, X) produit D. Si |X|+|F| = 0, alors c'est trivial, car D = S dans ce cas et on produit D à l'étape 1. On suppose que l'affirmation est vraie pour, ne produit que des ensembles irredondants maximaux. On montre alors que ENUMIS-I

, Afin d'analyser le temps d'exécution, on associe à chaque règle de branchement de l'algorithme, un vecteur de branchement où la mesure d'une instance (S, F, X) est définie par la somme |F| + |X| = |V(H)|. Donc il suffit d'analyser les étapes correspondant aux règles de branchement : les étapes, pp.6-7

, On suppose par contradiction qu'il existe un i ? |W| ? 1 tel que D ? N(w i ) ? N(w i +1 ) = . On considère le sous-graphe induit H = G

O. Ensuite, W. Montre-que-h-=-(u, E. , H. , W. et al., Il n'est pas difficile de constater qu'il n'existe aucune arête w j u ? E tel que w j ? W , u ? U ou w j ? W , u ? U , sinon u ? N(w i ) ? N(w i +1 ). Par conséquent, les deux sous-graphes induits H et H sont en effet deux composantes connexes de H. Par l'observation 3, N(w i ) ? D = et N(w i +1 )

. D&apos;une-façon-similaire,

, Pour deux consécutifs w i

. ?-d-?-u,-alors-i-i-?-i-j-?-d-=, Lemme 17. Soient i , j ? U tels que I i ? I j = . S'il existe un k ? U tel que I k ? (I i ? I j ) et i , j , k

. Démonstration, ?. Soient, and . D?u,-i-i-?i-j-=-et-i-k-?-{i-i-?i-j-}, On suppose par contradiction qu'il existe un w ? D?I i ?I j . Il est clair que le sommet k est un point d'articulation de G[D]. Par conséquent, il y a w x , w x ? D ? I k et w x

, Sans perte de généralité, on suppose que w x ? I i ? I k \ I j et w x ? I j ?I k \I i . Toutefois, il existe un chemin w x ? w x passant par i , w, j sans passer par k

, Lemme 18. Soient i , j ? D ? U tels que I i ? I j = . Alors |{k ? D : I k ? (I i ? I j )}| ? 1

. Démonstration and . Soient-i-,-j-?-d,-i-i-?-i-j-=, On suppose par contradiction qu'il existe k, l ? D satisfaisant I k ? {I i ? I j } et I l ? {I i ? I j }. Par les lemmes 14 et 13 et sans restreindre la généralité, on suppose que l (I i ) < l (I k ) < l (I l ) < l (I j ) et r (I i ) < r (I k ) < r (I l ) < r (I j )

. Comme-k-est-un-point-d&apos;articulation-de-g[d] and . Existe-w-x-,-w-x-?-d-?-i-k-et-w-x, De plus, au moins l'un de deux sommets n'appartient pas à I l . Sans perte de généralité, soit w x < w x et w x ? I l . Comme l est un point d'articulation de G[D], alors il existe w y , w y ? D ? I l et w

, Il est clair que l'un de w y , w y est non adjacent à k. Sans perte de généralité, on suppose que w y > w y et w y > r (I k )

, De plus, w y < l (I j ) et w y > w x sinon w x , w x seront adjacents à l et w y , w y seront adjacents à j . On peut déduire aussi que w x > r (I i ) (voir la figure 4.4). Par conséquent, il existe un chemin w y ? w y passant par k, w x

, Dans la section suivante, on présente l'algorithme d'énumération des ensembles dominants connexes minimaux dans les graphes bipartis convexes qui se base sur les propriétés structurelles ci-dessus

, L'algorithme d'énumération L'algorithme d'énumération consiste à sélectionner les sommets d'un ensemble dominant connexe minimal D par des règles de réduction et de branchement

}. U-\-{-j, S. ?-{-j-}, T. , and F. ). , Si d eg (r ) = 1, alors soit { j } = N(r ) et appelez ENUMLEVEL2( j

, Si d eg (r ) = 2, alors soit { j , k} = N(r ) et branchez : Si I j ? I k ou I k ? I j, vol.alors branchez

S. Appelez-enumlevel2(-j-,-u-\-{-j-,-k}, F. ?-{-j-},-t-?-{k}, T. )-;-u-\-{-j-,-k},-s-?-{k}, }. ?-{-j, and F. , (ii) appelez ENUMLEVEL2(k

, Sinon, soit r ( j ) > r (k) et branchez

S. Appelez-enumlevel2(-j-,-u-\-{-j-,-k}, F. ?-{-j-},-t-?-{k}, T. )-;-u-\-{-j-,-k},-s-?-{k}, }. ?-{-j, F. )-;-u-\-{-j-,-k} et al., (ii) appelez ENUMLEVEL2(k

S. ?-{-j, }. , T. ?-n(r-)-\-{-j, }. , F. et al., ii) pour chaque x ? N(r ) tel que l (I u ) < l (I x ) < l (I j ) et r (I u ) < r (I x ) < r (I j ), appelez ENUMLEVEL2( j , U \ N(r, Etape 6. Si d eg (r ) ? 3, alors soit j l'adjacent de r qui a la plus grande extrémité droite et branchez : (i) appelez ENUMLEVEL2( j , U \ N(r )

S. Appelez-enumlevel2(u,-u-\-{-j-}, T. ?-{-j, }. , and F. ,

, Soit j le voisin de r avec la plus grande extrémité droite

S. , ?. Dans-le-cas-;-u,-u-\-{-j-}, S. , T. ?-{-j, }. et al., On suppose maintenant que N(r ) ? D \ {u, j } = . Dans ce cas, comme l'étape 1 est non applicable et par les lemmes 13 et 14, on a pour tout x ? D ? N(r ) \ {u, j }, l (I u ) < l (I x ) < l (I j ) et r (I u ) < r (I x ) < r (I j ). Comme I x ? (I u ? I j ) et par le lemme 18, |N(r ) ? D \ {u, j }| ? 1, alors on a |N(r ) ? D \ {u, j }| = 1. On suppose que N(r ) ? D \ {u, j } = {x}. Dans ce cas, on interdit par le lemme 17 (I j ? I u ). Par conséquent, on branche pour chaque x ? N(r ) satisfaisant l (I u ) < l (I x ) < l (I j ) et r (I u ) < r (I x ) < r (I j ), on ajoute j à T afin de le dominer dans les prochaines étapes par les sommets de W. Par conséquent, on appelle ENUMLEVEL2

, S'il existe un x ? U tel que I x ? I j , alors x sera traité par l'étape 1 de l'appel récursif. Si d eg (w) = 3, alors F ? F ? {w}

, Etape 3. Tant que ( I = ) Debut

I. Soit, intervalle qui a l'extrémité droite le plus à gauche dans I et on désigne r (I i ) par r

}. Si-i-=-{i-i and F. ). ,

, Sinon si d eg (r ) = 2, alors soit N(r ) = {i

. I-?-i-\-i-i,

, Sinon si d eg (r ) = 3, alors soit N(r ) = {i , j , k}, I j l'intervalle qui a la plus grande extrémité et I k l'autre intervalle tel que I k ? (I i ? I j

J. , S. , and S. {i-i-?-i-k-\-i-j-}-?-{i-j-?-i-k-\-i-i-},

. I-?-i-\-i-i-.-fin,

T. La-procédure-enumlevel3(s, étape 1 et 2, les solutions partielles S qui ne peuvent pas être étendues à des ensembles dominants connexes minimaux de G. A l'étape 1, s'il existe u, v ? S ? U tels que I u ? I v , alors on s'arrête car par le lemme 13, la solution partielle S ? D. A l'étape 2, on vérifie chaque sommet w ? W

, Dans un premier temps, chaque sommet de T devrait être dominé par au moins un de ses voisins. Alors, on a initialisé J(T, S) par un ensemble d'intervalles où les voisins de chaque sommet de T sont représentés par un intervalle

;. Ensuite, J. , and F. ). , Comme d eg (r ) ? 3, à cause de l'étape 2, alors il ne nous reste que deux possibilités : soit d eg (r ) = 2, soit d eg (r ) = 3. Si d eg (r ) = 2, on suppose par contradiction que I i ? I j ? D = . Par l'observation 3, il y a un w i ? I i ? D et un w j ? I j ? D

T. , S. , and S. {i-i-?-i-j-}, Comme d eg (r ) = 2, alors on ne peut pas avoir un u ? U ? D tel que u ? N(w i ) ? N(w j ), une contradiction avec le lemme 16. Donc on peut déduire que I i ? I j ? D = . Par conséquent, J

, On rappelle qu'on a prouvé avec ce graphe que la borne inférieure des ensembles tropicaux connexes minimaux est au moins 1.4916 n . On rappelle aussi qu'un graphe est dit cordal si chacun de ses cycles de quatre sommets ou plus possède une corde

. Démonstration, E. ). Soit-g-=-(v, and L. Graphe, chaque sommet z ? C appartient à une clique (soit un K 5 soit un K 3 ) qui correspond à un sommet v de l'arbre T. Etant donné un tel sommet z, on désigne par f (z), son sommet correspondant v dans T. Soit x ? C tel que f (x) est le sommet le plus profond (i.e. le plus bas) de l'arbre T. Il est clair que f (x) n'est pas la racine de T, sinon C est une clique. Donc f (x) a un parent dans bien que le cycle C ne peut pas avoir trois sommets consécutifs x, y, z tels que f (x) = f (y) = f (z), sinon dans ce cas les sommets x, y, z appartiennent à la même clique, et par conséquent C n'est pas un cycle induit. On suppose tout d'abord que le sommet consécutif de x dans C est le sommet y tel que f (x) = f (y)

, Cette dernière démonstration, nous permet de déduire le lemme suivant

, Dans la section suivante, on a étudié les ensembles tropicaux connexes minimaux dans les graphes scindés

, Un graphe G = (K, I, E) est dit scindé si l'ensemble de ses sommets V peut être par

L. Kratsch and . Sayadi,

. L&apos;idée-principale-de-l&apos;algorithme-est-que-lorsqu&apos;on-sélectionne-un-sommet-x-?-k, Afin d'optimiser le temps d'exécution, les auteurs de l'article [51] ont analysé le temps d'exécution avec la technique Mesurer pour Conquérir. Ils ont associé à l'instance du problème (K, I, T, S) une mesure de |K| + |I| + |T| · w, où w = 0.533244. Autrement dit, si on sélectionne un sommet de la clique K, la mesure de l'instance diminue de 1. Par contre, si on déplace un sommet du stable I à T

. .. Résumé,

, est le premier algorithme d'énumération « input-sensitive » établi pour une sousclasse non triviale de graphes bipartis qui concernent l'ensemble dominant minimal et ses variants. On a conçu aussi des algorithmes d'énumération des ensembles irredondants maximaux dans les graphes cordaux, les graphes d'intervalles

. Finalement, Contrairement à l'énumération « input-sensitive », la complexité des problèmes d'énumération « output-sensitive » est bien étudiée et les algorithmes sont classés selon le délai entre deux solutions consécutives. Alors que la classification des problèmes d'énumération « input-sensitive » semble ne pas avoir de sens ou n'existe pas. Pour cela, on a essayé durant cette thèse de varier la nature de la contrainte et les classes de graphes. Tout d'abord, on a commencé par l'étude, dans le chapitre 2, des ensembles dominants minimaux où la contrainte de dominance est une contrainte locale. Puis dans le chapitre 3, on a étudié l'énumération des ensembles irredondants maximaux. Et contrairement à un ensemble dominant minimal, on a étudié un nouvel ensemble défini récemment : L'encobipartis, les graphes d'intervalles et les graphes blocs

. Finalement, On note bien que les techniques utilisées pour résoudre les problèmes d'énumération « input-sensitive » jusqu'à nos jours, soit dans cette thèse soit dans les différents articles publiés, sont principalement « Brancher et réduire » et « Mesurer pour Conquérir ». Uniquement ces deux techniques, parmi les différentes techniques connues des algorithmes exponentiels, semblent bonnes pour résoudre ce type de problème. Dans la limite des techniques utilisées, c'est assez courant dans l'énumération « inputsensitive » d'avoir un grand écart entre la borne supérieure et la borne inférieure. Donc 5.1 Résumé Moon et Moser ont prouvé que le nombre maximum des ensembles stables maxiborne, appelée borne supérieure, est stricte vu l'existence d'une famille des graphes avec un tel nombre appelée borne inférieure. Au contraire de l'énumération des ensembles stables maximaux, avoir deux bornes qui se coïncident n'est pas évident du tout. Et c'est assez courant dans l'énumération « input-sensitive » d'avoir un grand écart, énumération des ensembles dominants connexes minimaux et des ensembles tropicaux connexes minimaux où la contrainte de connexité est une contrainte globale. De même, on a essayé d'étudier l'énumération de ces ensembles dans différentes classes de graphes. Alors on a réussi à concevoir des algorithmes d'énumération dans les graphes d'intervalles, les forêts, les graphes bipartis convexes. . . , mais surtout dans les graphes cordaux où on a établi une nouvelle propriété

T. Durant-cette, On a étudié aussi l'énumération des ensembles dominants connexes minimaux et les ensembles irredondants maximaux qui sont très proches des ensembles dominants minimaux. On a proposé un algorithme d'énumération des ensembles dominants connexes minimaux dans les graphes bipartis convexes en O (1.7254 n ). D'une part c'est déjà un progrès par rapport à la borne précédente, celle d'un graphe général, qui est en O (2 (1? )n ) où > 10 ?50 . D'autre part, c'est le premier algorithme d'énumération « input-sensitive » établi pour une sousclasse non triviale de graphes bipartis qui concernent l'ensemble dominant minimal et ses variants, énumérer tous les ensembles dominants minimaux dans les graphes cordaux en O (1.5048 n )

V. Afin-de, ensemble défini récemment : L'ensemble tropiles graphes cobipartis, les graphes d'intervalles et les graphes blocs. Finalement, comme perspective et pour attirer l'attention de la communauté sur l'énumération des ensembles dominants totaux minimaux

F. N. Abu-khzam and P. Heggernes, Enumerating minimal dominating sets in chordal graphs, Inf. Process. Lett, vol.116, p.27, 2016.

F. N. Abu-khzam, A. E. Mouawad, and M. Liedloff, An exact algorithm for connected red-blue dominating set, J. Discrete Algorithms, vol.9, p.3, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00607125

, , vol.72, p.96

J. Bang-jensen, J. Huang, G. Macgillivray, and A. Yeo, «Domination in convex bipartite and convex-round graphs», cahier de recherche, 1999.

R. Bellman, Dynamic programming treatment of the travelling salesman problem, J. ACM, vol.9, issue.1, pp.61-63, 1962.

B. Bergougnoux, F. Capelli, and M. M. Kanté, «Counting minimal transversals of ?-acyclic hypergraphs, J. Comput. Syst. Sci, vol.101, pp.21-30, 2019.

D. Binkele-raible, L. Brankovic, M. Cygan, H. Fernau, J. Kneis et al., Breaking the 2 n -barrier for irredundance : Two lines of attack, J. Discrete Algorithms, vol.9, p.96, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00607123

M. Bonamy, O. Defrain, M. Heinrich, and J. R. , «Enumerating minimal dominating sets in triangle-free graphs, dans 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, vol.16, p.12, 2019.

K. S. Booth and J. H. Johnson, «Dominating sets in chordal graphs, SIAM J. Comput, vol.11, pp.191-199, 1982.

E. Boros, Generating maximal irredundant and minimal redundant subfamilies of hypergraphs, WEPA 2016 : First Workshop on Enumeration Problems and Applications 21-22, p.46, 2016.

A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph Classes : A Survey, vol.3, 1999.

N. Caspard, B. Leclerc, and B. Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, vol.60, 2007.

M. Chang, P. Nagavamsi, and C. Rangan, «Weighted irredundance of interval graphs, Information Processing Letters, vol.66, issue.2, pp.65-70, 1998.

M. Chapelle, M. Cochefert, D. Kratsch, R. Letourneur, and M. Liedloff, Exact exponential algorithms to find tropical connected sets of minimum size, Theor. Comput. Sci, vol.676, pp.33-41, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01971120

V. Chvátal and P. L. Hammer, Set-packing and threshold graphs, 1973.

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

J. Couturier, P. Heggernes, P. Van-&apos;t-hof, and D. Kratsch, «Minimal dominating sets in graph classes : Combinatorial bounds and enumeration, dans SOF-SEM 2012 : Theory and Practice of Computer Science -38th Conference on Current Trends in Theory and Practice of Computer Science, pp.202-213, 2012.

,

J. Couturier, P. Heggernes, P. Van-&apos;t-hof, and D. Kratsch, «Minimal dominating sets in graph classes : Combinatorial bounds and enumeration, Theor. Comput. Sci, vol.487, p.91, 2013.

J. Couturier, R. Letourneur, and M. Liedloff, «On the number of minimal dominating sets on some graph classes, Theor. Comput. Sci, vol.562, 2015.

, , vol.42, p.69

P. Damaschke, H. Müller, and D. Kratsch, «Domination in convex and chordal bipartite graphs, Inf. Process. Lett, vol.36, pp.231-236, 1990.

D. , J. A. , N. Cohen, H. E. Mafthoui, A. Harutyunyan et al., Connected tropical subgraphs in vertex-colored graphs, vol.17, p.73, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01077567

G. A. Dirac, On rigid circuit graphs», dans Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol.25, p.58, 1961.

M. Fellows, G. Fricke, S. Hedetniemi, and D. Jacobs, «The private neighbor cube, SIAM Journal on Discrete Mathematics, vol.7, pp.41-47, 1994.

H. Fernau, P. A. Golovach, and M. Sagot, «Algorithmic enumeration : Output-sensitive , input-sensitive , parameterized , approximative, p.69, 2018.

F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov, «Combinatorial bounds via measure and conquer : Bounding minimal dominating sets and applications, ACM Trans. Algorithms, vol.5, p.74, 2008.

F. V. Fomin and D. Kratsch, Exact Exponential Algorithms, Texts in Theoretical Computer Science. An EATCS Series, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00085561

, , p.39

M. L. Fredman and L. Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, vol.21, pp.618-628, 1996.

M. R. Garey and D. S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979.

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.

E. Georgii, S. Dietmann, T. Uno, P. Pagel, and K. Tsuda, «Enumeration of condition-dependent dense modules in protein interaction networks, Bioinformatics, vol.25, pp.933-940, 2009.

P. A. Golovach, P. Heggernes, M. M. Kanté, D. Kratsch, and Y. Villanger, «Enumerating minimal dominating sets in chordal bipartite graphs, Discrete Applied Mathematics, vol.199, pp.30-36, 2016.

P. A. Golovach, P. Heggernes, M. M. Kanté, D. Kratsch, and Y. Villanger, «Minimal dominating sets in interval graphs and trees, Discrete Applied Mathematics, vol.216, pp.162-170, 2017.

P. A. Golovach, P. Heggernes, and D. Kratsch, «Enumerating minimal connected dominating sets in graphs of bounded chordality, Theor. Comput. Sci, vol.630, p.96, 2016.

P. A. Golovach, P. Heggernes, D. Kratsch, and R. Saei, «Enumeration of minimal connected dominating sets for chordal graphs, vol.69, p.91

P. A. Golovach, D. Kratsch, M. Liedloff, M. Rao, and M. Y. Sayadi, «On maximal irredundant sets and (?, )-dominating sets in paths, WEPA 2016 : First Workshop on Enumeration Problems and Applications, vol.44, p.69, 2016.

P. A. Golovach, D. Kratsch, and M. Y. Sayadi, «Enumeration of maximal irredundant sets for claw-free graphs, Theoretical Computer Science, vol.754, p.74, 2019.

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

B. Gras and M. Liedloff, Enumeration of minimal connected dominating sets in chordal bipartite graphs, Proceedings of the 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, p.91, 2019.

F. Harary, A characterization of block-graphs», vol.6, p.87, 1963.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in graphs : Advanced topics, p.24, 1997.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs, p.24, 1998.

S. Hedetniemi, R. Laskar, and J. Pfaff, Irredundance in graphs : a survey, vol.48, pp.183-193, 1985.

E. Howorka and . Graphs*», The Quarterly Journal of Mathematics, vol.28, pp.417-420, 1977.

Y. Iwata, A faster algorithm for dominating set analyzed by the potential method», dans Parameterized and Exact Computation, p.46, 2012.

M. S. Jacobson and K. Peters, «Chordal graphs and upper irredundance, upper domination and independence, Discrete Mathematics, vol.86, pp.59-69, 1990.

Y. Jing-ho, C. Jer-jeong, and G. J. Chang, Quasi-threshold graphs, vol.69, pp.247-255, 1996.

M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine, «On the enumeration of minimal dominating sets and related notions, SIAM Journal on Discrete Mathematics, vol.28, p.72, 2014.

M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, and T. Uno, On the enumeration and counting of minimal dominating sets in interval and permutation graphs», dans Algorithms and Computation, pp.339-349, 2013.

M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, and T. Uno, «A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs», dans Graph-Theoretic Concepts in Computer Science -41st International Workshop, pp.138-153, 2015.

R. M. Karp, Reducibility among combinatorial problems, pp.85-103, 1972.

B. Korte and J. Vygen, Combinatorial Optimization, p.87, 2018.

D. Kratsch, M. Liedloff, and M. Y. Sayadi, Enumerating minimal tropical connected sets, dans SOFSEM 2017 : Theory and Practice of Computer Science -43rd International Conference on Current Trends in Theory and Practice of Computer Science, vol.84, p.91, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01971055

M. Krzywkowski, «Trees having many minimal dominating sets, Inf. Process. Lett, vol.113, issue.8, pp.276-279, 2013.

R. Laskar and J. Pfaff, «Domination and irredundance in split graphs. technicial report 430, clemson university, dept. math, p.44, 1983.

D. Lokshtanov, M. Pilipczuk, and S. Saurabh, «Below all subsets for minimal connected dominating set, SIAM Journal on Discrete Mathematics, vol.32, p.91, 2018.

J. W. Moon and L. Moser, «On cliques in graphs, Israel J. Math, vol.3, p.94, 1965.

H. Müller and A. Brandstädt, «The np-completeness of steiner tree and dominating set for chordal bipartite graphs, Theoretical Computer Science, vol.53, issue.2-3, pp.257-265, 1987.

J. Pfaff, R. Laskar, and S. Hedetniemi, «Np-completeness of total and connected domination and irredundance for bipartite graphs, Tech. Rept, vol.428, 1983.

J. Puech, «Irredundance perfect and p6-free graphs, Journal of Graph Theory, vol.29, issue.4, pp.239-255, 1998.

G. Rote, «The maximum number of minimal dominating sets in a tree, dans Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, vol.42, p.69, 2019.

J. Schmidt, Enumeration : Algorithms and complexity, mémoire de maîtrise, p.19, 2009.

I. B. Skjørten, Faster enumeration of minimal connected dominating sets in split graphs, mémoire de maîtrise, vol.42, p.91, 2017.

R. Tarjan, «Depth-first search and linear graph algorithms, SIAM journal on computing, vol.1, issue.2, pp.146-160, 1972.