Please use this identifier to cite or link to this item: http://hdl.handle.net/10077/33308
Title: Random generation of essential directed acyclic graphs
Authors: Rizzi, Romeu
Tomescu, Alexandru I.
Keywords: Directed acyclic graphcounting recurrencesampling
Issue Date: 2021
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.
Journal: Rendiconti dell’Istituto di Matematica dell’Università di Trieste: an International Journal of Mathematics 
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.
Type: Article
URI: http://hdl.handle.net/10077/33308
ISSN: 0049-4704
eISSN: 2464-8728
DOI: 10.13137/2464-8728/33308
Rights: Attribution-NonCommercial-NoDerivatives 4.0 Internazionale
Appears in Collections:Rendiconti dell’Istituto di Matematica dell’Università di Trieste: an International Journal of Mathematics vol.53 (2021)

Files in This Item:
File Description SizeFormat
22_RizziTomescu.pdf371.64 kBAdobe PDFThumbnail
View/Open
Show full item record


CORE Recommender

Page view(s)

66
checked on May 16, 2022

Download(s)

4
checked on May 16, 2022

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons