DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.3

Efficient Sampling of Increasing Trees

Authors: Nadja Azzouz, Olivier Bodini, Francis Durand, and Bernhard Gittenberger

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

We present a new exact-size sampler for increasing trees that outputs a tree of size n uniformly at random while avoiding the global coefficient pre-computation required by the classical recursive method of Flajolet et al. [Philippe Flajolet et al., 1994]. The key idea is a hybrid oracle-driven rejection scheme in which local sampling decisions are made using interval bounds on the coefficients, with a fallback to exact recurrence computation only on rare ambiguous events. In the bit-complexity model this yields an expected running time of O(nlog n) and it consumes a number of random bits within O(n) of the Shannon entropy, which is information-theoretically optimal up to lower-order terms. The sampler proceeds in two phases. We first generate the unlabeled rooted ordered shape by recursively sampling node arities and subtree sizes and then draw a uniform permutation of {1,…,n} and apply a deterministic increasing-labeling procedure.

Cite as

Nadja Azzouz, Olivier Bodini, Francis Durand, and Bernhard Gittenberger. Efficient Sampling of Increasing Trees. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{azzouz_et_al:LIPIcs.AofA.2026.3,
  author =	{Azzouz, Nadja and Bodini, Olivier and Durand, Francis and Gittenberger, Bernhard},
  title =	{{Efficient Sampling of Increasing Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.3},
  URN =		{urn:nbn:de:0030-drops-262740},
  doi =		{10.4230/LIPIcs.AofA.2026.3},
  annote =	{Keywords: sampling algorithms, bit-complexity, increasing trees, generating functions}
}

Document

DOI: 10.4230/LIPIcs.AofA.2026.30

Asymptotic Analysis of Generating Functions Arising from Dynamic Graphs

Authors: Nadja Azzouz, Olivier Bodini, Francis Durand, and Bernhard Gittenberger

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

We study generating functions arising from sequentially growing labeled graphs where at each step either a new vertex is created or a new edge between two existing vertices is added. We provide explicit representations of the generating functions and derive asymptotic formulas for their coefficients using Laplace’s method and Bessel function approximations in the undirected model, and Hayman admissibility combined with the saddle point method in the directed model. Finally, we study a natural parameter of each model and indicate further parameter studies.

Cite as

Nadja Azzouz, Olivier Bodini, Francis Durand, and Bernhard Gittenberger. Asymptotic Analysis of Generating Functions Arising from Dynamic Graphs. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{azzouz_et_al:LIPIcs.AofA.2026.30,
  author =	{Azzouz, Nadja and Bodini, Olivier and Durand, Francis and Gittenberger, Bernhard},
  title =	{{Asymptotic Analysis of Generating Functions Arising from Dynamic Graphs}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.30},
  URN =		{urn:nbn:de:0030-drops-263010},
  doi =		{10.4230/LIPIcs.AofA.2026.30},
  annote =	{Keywords: combinatorial enumeration, generating functions}
}

Search Results

Documents authored by Durand, Francis

Efficient Sampling of Increasing Trees

Abstract

Cite as

Asymptotic Analysis of Generating Functions Arising from Dynamic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message