Search Results

Documents authored by Bodini, Olivier

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}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.13
Asymptotic Distribution of Parameters in Random Maps

Authors: Olivier Bodini, Julien Courtiel, Sergey Dovgal, and Hsien-Kuei Hwang

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.
Cite as

Olivier Bodini, Julien Courtiel, Sergey Dovgal, and Hsien-Kuei Hwang. Asymptotic Distribution of Parameters in Random Maps. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.AofA.2018.13,
  author =	{Bodini, Olivier and Courtiel, Julien and Dovgal, Sergey and Hwang, Hsien-Kuei},
  title =	{{Asymptotic Distribution of Parameters in Random Maps}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.13},
  URN =		{urn:nbn:de:0030-drops-89069},
  doi =		{10.4230/LIPIcs.AofA.2018.13},
  annote =	{Keywords: Random maps, Analytic combinatorics, Rooted Maps, Beta law, Limit laws, Patterns, Generating functions, Riccati equation}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.14
Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes

Authors: Olivier Bodini, Matthieu Dien, Antoine Genitrini, and Alfredo Viola

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process is a directed acyclic graph (DAG). Since the quantitative study of increasingly labeled DAG (directly related to processes) seems out of reach (this is a #P-complete problem), we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the classical sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of a uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.
Cite as

Olivier Bodini, Matthieu Dien, Antoine Genitrini, and Alfredo Viola. Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.AofA.2018.14,
  author =	{Bodini, Olivier and Dien, Matthieu and Genitrini, Antoine and Viola, Alfredo},
  title =	{{Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.14},
  URN =		{urn:nbn:de:0030-drops-89075},
  doi =		{10.4230/LIPIcs.AofA.2018.14},
  annote =	{Keywords: Concurrency Theory, Future, Uniform Random Sampling, Unranking, Analytic Combinatorics}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.425
The Combinatorics of Non-determinism

Authors: Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
A deep connection exists between the interleaving semantics of concurrent processes and increasingly labelled combinatorial structures. In this paper we further explore this connection by studying the rich combinatorics of partially increasing structures underlying the operator of non-deterministic choice. Following the symbolic method of analytic combinatorics, we study the size of the computation trees induced by typical non-deterministic processes, providing a precise quantitative measure of the so-called "combinatorial explosion" phenomenon. Alternatively, we can see non-deterministic choice as encoding a family of tree-like partial orders. Measuring the (rather large) size of this family on average offers a key witness to the expressiveness of the choice operator. As a practical outcome of our quantitative study, we describe an efficient algorithm for generating computation paths uniformly at random.
Cite as

Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski. The Combinatorics of Non-determinism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 425-436, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.FSTTCS.2013.425,
  author =	{Bodini, Olivier and Genitrini, Antoine and Peschanski, Fr\'{e}d\'{e}ric},
  title =	{{The Combinatorics of Non-determinism}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{425--436},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.425},
  URN =		{urn:nbn:de:0030-drops-43901},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.425},
  annote =	{Keywords: Concurrency theory, Analytic combinatorics, Non-deterministic choice, Partially increasing trees, Uniform random generation}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact