Résumé :

Minimal chordal completions of a graph, also called minimal triangulations, are an important object in graph theory. For some applications, e.g. to databases, it is useful to generate all minimal chordal completions of a graph as efficiently as possible. However, for efficiency we need to take into account the large (possibly exponential) number of solutions. This long-lasting problem was successfully addressed in 2017: Carmeli, Kenig, and Kimelfeld designed an efficient algorithm for the listing of all minimal chordal completions of a graph. Its total running time is polynomial in the number of solutions. However, for more efficiency, we aim at designing an algorithm running with polynomial delay: the time needed between two consecutive outputs should be polynomial in the input size only. In this talk, I will present a new enumeration algorithm for the minimal chordal completions of a graph, running with polynomial delay and exponential space. After that, the space usage will be addressed, and I will exhibit how to modify our algorithm so that it only needs polynomial space.