Résumé : Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. DAGs are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70's by Robinson. For keeping the density of such graphs under control, one needs to take its number of edges into account too. But the adaptation of Robinson's enumeration to achieve this leads to counting formulas based on the inclusion-exclusion principle, inducing a high computational cost for the uniform random sampling based on this formula. I will present two contributions. First the enumeration of a new class of DAGs, enriched with an independent ordering of the children of each vertex, according to their numbers of vertices and edges. A constructive recursive counting formula is obtained (i.e. without using the inclusion-exclusion principle) thanks to a new decomposition scheme. Then I will show the applicability of the method by proposing a constructive enumeration of Robinson's labelled DAGs, by vertices and edges, based on the same approach. The consequence of having such a formula is that efficient uniform random samplers can be derived for both models.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr