Random Generation of Directed Acyclic Graphs

DOI10.1016/S1571-0653(04)00394-4zbMATH Open1171.05339OpenAlexW2045768854MaRDI QIDQ3438982FDOQ3438982

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding a Minimum Circuit in a Graph
• Title not available (Why is that?)
• Counting acyclic digraphs by sources and sinks
• 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
• Uniform random generation of large acyclic digraphs
• Telling stories: enumerating maximal directed acyclic graphs with a constrained set of sources and targets
• 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
• Title not available (Why is that?)
• 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
• Generation of random chordal graphs using subtrees of a tree
• A dynamic topological sort algorithm for directed acyclic graphs
• 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)