Long and short paths in uniform random recursive dags

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 σsuch that S_n/log(n) tends to σin probability as n tends to infinity. We also show that max_{1 \le i \le n} S_i/log(n) tends to σin probability.

16 pages

References in corpus (2)

• The power of choice in network growth
• A functional limit theorem for the profile of search trees

Cited by in corpus (5)

• Depth properties of scaled attachment random recursive trees
• Longest path distance in random circuits
• The connectivity-profile of random increasing k-trees
• Renewal theory in analysis of tries and strings
• Approximation of Subgraph Counts in the Uniform Attachment Model