Long and short paths in uniform random recursive dags (Q2431087)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long and short paths in uniform random recursive dags |
scientific article |
Statements
Long and short paths in uniform random recursive dags (English)
0 references
8 April 2011
0 references
The authors' main concern is the model of the uniform random recursive \(k\)-directed acyclic graph. This random directed graph is constructed as follows. There is a root vertex labeled as 0 and each succesive node labeled from 1 to \(n\) is joined to \(k\) of the previous nodes chosen uniformly at random with replacement. The authors provide results about the length of a random path starting from a certain node and leading to the root node. In particular, they show convergence in probability to a certain constant which they provide explicitly. However, the main result of the paper regards the length of the shortest path to the root that starts at vertex \(n\). In particular, they show that when divided by \(\log n\), this converges in probability to a certain constant which is determined implicitly through a certain function. Moreover, they show that the maximum shortest distance also satisfies this.
0 references
recursive directed graphs
0 references
shortest paths
0 references
law of large numbers
0 references