Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910016452165632 |
|---|---|
| author | Gabryelski, Wojciech Gołȩbiewski, Zbigniew Pépin, Martin |
| author_facet | Gabryelski, Wojciech Gołȩbiewski, Zbigniew Pépin, Martin |
| contents | 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^2)$ operations and requests to a random generator. This was achieved by extending the Boltzmann model for graphical generating functions and by using various decompositions of directed acyclic graphs. The presented samplers improve upon the state-of-the-art algorithms in terms of theoretical complexity and offer a significant speed-up in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08471 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs Gabryelski, Wojciech Gołȩbiewski, Zbigniew Pépin, Martin Data Structures and Algorithms Discrete Mathematics Combinatorics 68R05, 68R10, 05A15, 68W40 G.2.1; G.2.2; F.2.2 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^2)$ operations and requests to a random generator. This was achieved by extending the Boltzmann model for graphical generating functions and by using various decompositions of directed acyclic graphs. The presented samplers improve upon the state-of-the-art algorithms in terms of theoretical complexity and offer a significant speed-up in practice. |
| title | Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 68R05, 68R10, 05A15, 68W40 G.2.1; G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2602.08471 |