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

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

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

• Counting acyclic digraphs by sources and sinks
• Finding a Minimum Circuit in a Graph
• 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?)
• On the number of labeled acyclic digraphs

Cited in

(26)

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

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)