moteur de recherche

Séminaire Algo - Martin Pépin
Séminaire Algo - Martin Pépin
19-Jan-2021 14:00
Age: 41 days

Martin Pépin

Constructive enumeration and uniform random sampling of DAGs

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

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. In many applications one needs to construct connected DAGs and to control their number of edges, but the adaptation of Robinson's enumeration to take this into account led 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 decomposition. The consequence of having such a formulas is that efficient uniform random samplers can be derived for both models.

<- Back to: Accueil