Long and short paths in uniform random recursive dags

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.

No reviews yet.

No comments yet.