1. Random generation of essential directed acyclic graphs
- Author
-
Rizzi, Romeo, Tomescu, Alexandru I., Department of Computer Science, Algorithmic Bioinformatics, and Bioinformatics
- Subjects
counting recurrence ,sampling ,05C80 ,68R10 ,05C20 ,05C30 ,113 Computer and information sciences ,Directed acyclic graph - 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.
- Published
- 2021
- Full Text
- View/download PDF