Generating connected acyclic digraphs uniformly at random

2004/03/25 by Guy Melancon, Melancon, Guy, Fabrice Philippe +1
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #G.3 #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0403040

6 pages

arxiv created 2004/03/25 · arxiv updated 2009/12/01

Abstract

We describe a simple algorithm based on a Markov chain process to generate simply connected acyclic directed graphs over a fixed set of vertices. This algorithm is an extension of a previous one, designed to generate acyclic digraphs, non necessarily connected.

Related

• Counting directed acyclic and elementary digraphs
• Fast generation of random connected graphs with prescribed degrees
• Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
• Uniform random posets
• Enumerating Markov Equivalence Classes of Acyclic Digraph Models