Skip to Main content Skip to Navigation

Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive

Abstract : Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^{n/3}. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound. Unlike the enumeration of maximal independent sets, having a tight bounds is not obvious at all. And it’s quite common in the “input-sensitive” enumeration to have a big gap. This problem concerns even the most studied sets as minimal dominating sets where the best known algorithm to enumerate those sets runs in time O(1.7159^n) and the best known lower bound is only 1.5704^n. During this thesis, we proposed a "Measure and Conquer" algorithm to enumerate all minimal dominating sets for chordal graphs in time O(1.5048^n). Minimal connected dominating sets and maximal irredundant sets, which are closely related to minimal dominating sets, were also studied. An enumeration algorithm of minimal connected dominating sets in convex bipartite graphs has been proposed with a running time in O(1.7254^n). Enumeration algorithms of maximal irredundant sets have also been given for chordal graphs, interval graphs, and forests in times O(1.7549^n), O(1.6957^n) and O(1.6181^n) respectively instead of the trivial algorithm in time O*(2^n). We complement these upper bounds by showing that there are forest graphs with Omega(1.5292^n) maximal irredundant sets. We proved also that every maximal irredundant set of a cograph is a minimal dominating set. This implies that the maximum number of those sets in cographs is Theta(15^{n/6}). Finally, to vary, we studied a new set has been defined recently: The minimal tropical connected set. A lower bound of 1.4961^n has been proposed but we failed to improve the upper bound of 2^n. Enumeration algorithms of minimal tropical connected sets have been given for cobipartite, interval and block graphs in times O*(3^{n/3}), O(1.8613^n) and O*(3^{n/3}) respectively. A lower bound of 1.4766^n for splits graphs and 3^{n/3} for cobipartite, interval graphs and block graphs have been provided. We proposed a new lower bound of 1.5848^n, as a perspective and in order to draw community attention to the maximum number of minimal total dominating sets.
Complete list of metadatas

Cited literature [123 references]  Display  Hide  Download
Contributor : Thèses Ul <>
Submitted on : Monday, June 8, 2020 - 4:51:32 PM
Last modification on : Tuesday, June 9, 2020 - 3:17:19 AM


Files produced by the author(s)


  • HAL Id : tel-02860933, version 1



Mohamed Yosri Sayadi. Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive. Informatique [cs]. Université de Lorraine, 2019. Français. ⟨NNT : 2019LORR0316⟩. ⟨tel-02860933⟩



Record views


Files downloads