106 citations · 234 across the 33 of their papers we have counts for
6 papers · 2 filters
Cutting down trees with a Markov chainsaw
Louigi Addario-Berry, Nicolas Broutin, Cecilia Holmgren
We provide simplified proofs for the asymptotic distribution of the number of cuts required to cut down a Galton-Watson tree with critical, finite-variance offspring distribution,…
Asymptotics of trees with a prescribed degree sequence and applications
Nicolas Broutin, Jean-François Marckert
Let be a rooted tree and the number of nodes in having children. The degree sequence of satisfies $\sum_{i\ge 0} n_i(t)=1+\sum_{i\ge 0}…
Partial match queries in random quadtrees
Nicolas Broutin, Ralph Neininger, Henning Sulzbach
We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the d…
Connectivity threshold for Bluetooth graphs
Nicolas Broutin, Luc Devroye, Nicolas Fraiman +1
We study the connectivity properties of random Bluetooth graphs that model certain "ad hoc" wireless networks. The graphs are obtained as "irrigation subgraphs" of the well-known r…
The total path length of split trees
Nicolas Broutin, Cecilia Holmgren
We consider the model of random trees introduced by Devroye [SIAM J. Comput. 28 (1999) 409-432]. The model encompasses many important randomized algorithms and data structures. The…
Longest path distance in random circuits
Nicolas Broutin, Omar Fawzi
We study distance properties of a general class of random directed acyclic graphs (DAGs). In a DAG, many natural notions of distance are possible, for there exists multiple paths b…