Long and short paths in uniform random recursive dags
From MaRDI portal
Publication:2431087
DOI10.1007/S11512-009-0118-0zbMATH Open1230.60092arXiv0906.0152OpenAlexW2049562387MaRDI QIDQ2431087FDOQ2431087
Authors: Svante Janson, Luc Devroye 
Publication date: 8 April 2011
Published in: Arkiv för Matematik (Search for Journal in Brave)
Abstract: In a uniform random recursive k-dag, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S_n is the shortest path distance from node n to the root, then we determine the constant sigma such that S_n/log(n) tends to sigma in probability as n tends to infinity. We also show that max_{1 le i le n} S_i/log(n) tends to sigma in probability.
Full work available at URL: https://arxiv.org/abs/0906.0152
Recommendations
Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)
Cites Work
- A note on two problems in connexion with graphs
- Emergence of Scaling in Random Networks
- Title not available (Why is that?)
- On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
- A note on the height of binary search trees
- Chernoff's theorem in the branching random walk
- Probability Inequalities for Sums of Independent Random Variables
- On the distribution of leaves in rooted subtrees of recursive trees
- Title not available (Why is that?)
- Breaking Records and Breaking Boards
- Branching processes in the analysis of the heights of trees
- Distribution of nodes of a tree by degree
- Title not available (Why is that?)
- Note on the heights of random recursive trees and random m‐ary search trees
- Large deviations for the weighted height of an extended class of trees
- On the Altitude of Nodes in Random Trees
- A functional limit theorem for the profile of search trees
- Title not available (Why is that?)
- Profiles of random trees: Plane-oriented recursive trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- The power of choice in growing trees
- Limiting Distributions for Path Lengths in Recursive Trees
- Applications of the theory of records in the study of random trees
- Universal Limit Laws for Depths in Random Trees
- Title not available (Why is that?)
- Profiles of random trees: plane-oriented recursive trees
- Distances in random plane-oriented recursive trees
- A Probability Model of a Pyramid Scheme
- Title not available (Why is that?)
- A note on the growth of random trees
- A functional limit law for the profile of plane-oriented recursive trees
Cited In (12)
- Depth properties of scaled attachment random recursive trees
- An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- Shape measures of random increasing \(k\)-trees
- Longest path distance in random circuits
- Bounding variance and expectation of longest path lengths in dags
- On martingale tail sums in affine two-color urn models with multiple drawings
- Archaeology of random recursive dags and Cooper-Frieze random networks
- The degree profile in some classes of random graphs that generalize recursive trees
- Renewal theory in the analysis of tries and strings
- The number of descendants in a random directed acyclic graph
- On the length of the shortest path in a sparse Barak-Erdős graph
- Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
This page was built for publication: Long and short paths in uniform random recursive dags
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431087)
