Random Generation of Directed Acyclic Graphs

DOI10.1016/S1571-0653(04)00394-4zbMath1171.05339OpenAlexW2045768854MaRDI QIDQ3438982

Guy Melançon, Isabelle Dutour, Mireille Bousquet-Mélou

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s1571-0653(04)00394-4

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Directed graphs (digraphs), tournaments (05C20)

Related Items (max. 100)

Generating connected acyclic digraphs uniformly at random ⋮ Uniform random posets ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ A Comparison of Random Task Graph Generation Methods for Scheduling Problems ⋮ Random Generation of Deterministic Acyclic Automata Using Markov Chains ⋮ Uniform random generation of large acyclic digraphs ⋮ Is hyper-extensionality preservable under deletions of graph elements? ⋮ Asymptotic enumeration of compacted binary trees of bounded right height

Cites Work

• Counting acyclic digraphs by sources and sinks
• On the number of labeled acyclic digraphs
• Finding a Minimum Circuit in a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Random Generation of Directed Acyclic Graphs