Random generation of essential directed acyclic graphs
Tomescu, Alexandru I.
A directed acyclic graph (DAG) is called essential if for every edge (u, v) it holds that the set of in-neighbors of u is different than the set of in-neighbors of v minus vertex u. Essential DAGs have applications in Bayesian networks, where a basic problem is to generate uniformly at random a labeled essential DAGs with a given number of vertices. In this paper we prove a new decomposition of essential DAGs, which entails: (i) a new counting recurrence, and (ii) a new random generation algorithm, that may be of potential use for their applications in Bayesian networks.
EUT Edizioni Università di Trieste
Romeo Rizzi, Alexandru I. Tomescu. "Random generation of essential directed acyclic graphs" in: "Rendiconti dell’Istituto di Matematica dell’Università di Trieste: an International Journal of Mathematics vol.53 (2021)", EUT Edizioni Università di Trieste, Trieste, 2021. pp.
Attribution-NonCommercial-NoDerivatives 4.0 Internazionale