Generating connected acyclic digraphs uniformly at random

DOI10.1016/j.ipl.2003.06.002zbMath1177.68155arXivcs/0403040OpenAlexW1963516735MaRDI QIDQ2390252

Fabrice Philippe, Guy Melançon

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0403040

zbMATH Keywords

graph algorithmsrandom generationsimply connected acyclic directed graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

Asymmetric hidden Markov models ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ Online estimation of discrete, continuous, and conditional joint densities using classifier chains ⋮ An effective genetic algorithm for network coding ⋮ 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

• The asymptotic number of acyclic digraphs. I
• Counting acyclic digraphs by sources and sinks
• Random Generation of Directed Acyclic Graphs
• On the shape of a random acyclic digraph
• Finding a Minimum Circuit in a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generating connected acyclic digraphs uniformly at random