Random Generation of Directed Acyclic Graphs

DOI10.1016/S1571-0653(04)00394-4MaRDI QIDQ3438982zbMATH OpenOpenAlexFDO

Authors G. 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

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

Recommendations

• Generating connected acyclic digraphs uniformly at random
• Uniform random generation of large acyclic digraphs
• Random generation of essential directed acyclic graphs
• The asymptotic number of acyclic digraphs. I
• Markov chain algorithms for generating sets uniformly at random

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 1146225 (Why is no real title available?)
• Counting acyclic digraphs by sources and sinks
• Finding a Minimum Circuit in a Graph
• On the number of labeled acyclic digraphs

Cited in

(24)

• Stratigraphy of a random acyclic directed graph: The size of trophic levels in the cascade model
• Increasing diamonds
• Asymptotic enumeration of compacted binary trees of bounded right height
• Telling stories: enumerating maximal directed acyclic graphs with a constrained set of sources and targets
• Uniform random generation of large acyclic digraphs
• Uniform random posets
• Efficient coding of labeled directed acyclic graphs
• Sampling different kinds of acyclic automata using Markov chains
• Ranking, unranking and random generation of extensional acyclic digraphs
• Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming
• A Family of Tree-Based Generators for Bubbles in Directed Graphs
• Is hyper-extensionality preservable under deletions of graph elements?
• Random generation of essential directed acyclic graphs
• On the shape of a random acyclic digraph
• The number of descendants in a random directed acyclic graph
• Random generation of deterministic acyclic automata using Markov chains
• scientific article; zbMATH DE number 2044702 (Why is no real title available?)
• Generating connected acyclic digraphs uniformly at random
• Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs
• Möbius Inversion of Random Acyclic Directed Graphs
• A dynamic topological sort algorithm for directed acyclic graphs
• Generation of random chordal graphs using subtrees of a tree
• Markov chain algorithms for generating sets uniformly at random
• A comparison of random task graph generation methods for scheduling problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3438982)