Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Cette thèse porte sur la théorie des graphes, des hypergraphes, et des treillis. Nous nous intéressons à la complexité du problème de dualisation des fonctions monotones Booléennes, ainsi qu’à ses généralisations, à travers les différentes formes qu’il prend dans ces structures: énumération des dominants minimaux, des transversaux minimaux, dualisation dans les treillis, et énumération des éléments meet-irréductibles. De nouveaux résultats positifs et négatifs sont obtenus, et des directions de recherche futures sont proposées. La thèse se découpe comme suit. Dans une première partie, nous nous intéressons à l’énumération des dominants minimaux dans les graphes. Nous obtenons de nouveaux algorithmes output-polynomiaux dans les graphes sans grande clique, et dans d’autres classes de graphes liées aux ordres partiels de dimension bornée. Dans une seconde partie, nous nous intéressons aux généralisations de ce problème dans les treillis. Une première généralisation concerne la dualisation dans les treillis donnés par une base d’implications, l’autre concerne l’énumération des éléments meet-irréductibles. Des résultats positifs et négatifs sont obtenus sous plusieurs contraintes concernant la largeur, l’acyclicité, et la taille des prémisses dans la base d’implication. Les deux parties de la thèse sont parsemées d’énumération des transversaux minimaux d’un hypergraphe, et de notions liées. ; This thesis focuses on graphs, hypergraphs, and lattices. We study the complexity of the dualization of monotone Boolean functions, and its generalizations, through the many shapes it takes on these structures: minimal dominating sets enumeration, minimal transversals enumeration, lattice dualization, and meet-irreducible enumeration. Both tractable and intractable results are obtained, and future research directions are proposed. The thesis is organized as follows. A first part is devoted to the enumeration of minimal dominating sets in graphs. We obtain new output-polynomial time algorithms in graph classes related to Kt-free ...