Seminars

In enumeration we are interested in generating a set of solutions, while bounding the time needed to generate one solution. We will first present the complexity measures used in this context, simple theoritical results and a few open questions.
We then introduce classical problems in this area such as the enumeration of: trees, models of a DNF, model of a FO or MSO formula, the maximal cliques of a graph, circuits of a matroid ...
We use them to illustrate the algorithmic toolbox of enumeration (Gray Code, backtrack search, reverse search, saturation...).