Options
Random generation of essential directed acyclic graphs
Rizzi, Romeu
Tomescu, Alexandru I.
2021
Loading...
e-ISSN
2464-8728
Abstract
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.
Publisher
EUT Edizioni Università di Trieste
Source
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.
Languages
en
Rights
Attribution-NonCommercial-NoDerivatives 4.0 Internazionale
File(s)