Long and short paths in uniform random recursive dags

Details Long and short paths in uniform random recursive dags Long and short paths in uniform random recursive dags

2009-05-31

arxiv.org/abs/0906.0152v1

Mathematics

Probability

16 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Long and short paths in uniform random recursive dags does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Long and short paths in uniform random recursive dags, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Long and short paths in uniform random recursive dags will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-708612