Long and short paths in uniform random recursive dags
From MaRDI portal
Publication:2431087
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3762080 (Why is no real title available?)
- scientific article; zbMATH DE number 17686 (Why is no real title available?)
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 1246231 (Why is no real title available?)
- scientific article; zbMATH DE number 741240 (Why is no real title available?)
- scientific article; zbMATH DE number 1372652 (Why is no real title available?)
- A Probability Model of a Pyramid Scheme
- A functional limit law for the profile of plane-oriented recursive trees
- A functional limit theorem for the profile of search trees
- A note on the growth of random trees
- A note on the height of binary search trees
- A note on two problems in connexion with graphs
- Applications of the theory of records in the study of random trees
- Branching processes in the analysis of the heights of trees
- Breaking Records and Breaking Boards
- Chernoff's theorem in the branching random walk
- Distances in random plane-oriented recursive trees
- Distribution of nodes of a tree by degree
- Emergence of Scaling in Random Networks
- Large deviations for the weighted height of an extended class of trees
- Limiting Distributions for Path Lengths in Recursive Trees
- Note on the heights of random recursive trees and random m‐ary search trees
- On the Altitude of Nodes in Random Trees
- On the distribution of leaves in rooted subtrees of recursive trees
- On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
- Probability Inequalities for Sums of Independent Random Variables
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- Profiles of random trees: Plane-oriented recursive trees
- Profiles of random trees: plane-oriented recursive trees
- The power of choice in growing trees
- Universal Limit Laws for Depths in Random Trees
Cited in
(12)- Bounding variance and expectation of longest path lengths in dags
- Longest path distance in random circuits
- Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
- Renewal theory in the analysis of tries and strings
- On martingale tail sums in affine two-color urn models with multiple drawings
- The number of descendants in a random directed acyclic graph
- Archaeology of random recursive dags and Cooper-Frieze random networks
- An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- On the length of the shortest path in a sparse Barak-Erdős graph
- Depth properties of scaled attachment random recursive trees
- The degree profile in some classes of random graphs that generalize recursive trees
- Shape measures of random increasing \(k\)-trees
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)
