Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs

Wojciech Gabryelski, Zbigniew Gołȩbiewski, Martin Pépin

We propose two efficient algorithms for generating uniform random directed acyclic graphs, including an asymptotically optimal exact-size sampler that performs $\frac{n^2}{2} + o(n…