Long and short paths in uniform random recursive dags

Luc Devroye School of Computer Science, McGill University Svante Janson Department of Mathematics, Uppsala University

Optimization and Control Probability mathscidoc:1701.27002

Arkiv for Matematik, 49, (1), 61-77, 2009.6
In a uniform random recursive$k$-directed acyclic graph, 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$→$σ$in probability as$n$→∞. We also show that max_{1≤$i$≤$n$}$S$_{$i$}/log$n$→$σ$in probability.
No keywords uploaded!
[ Download ] [ 2017-01-08 20:36:29 uploaded by arkivadmin ] [ 410 downloads ] [ 0 comments ]
@inproceedings{luc2009long,
  title={Long and short paths in uniform random recursive dags},
  author={Luc Devroye, and Svante Janson},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203629214220993},
  booktitle={Arkiv for Matematik},
  volume={49},
  number={1},
  pages={61-77},
  year={2009},
}
Luc Devroye, and Svante Janson. Long and short paths in uniform random recursive dags. 2009. Vol. 49. In Arkiv for Matematik. pp.61-77. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203629214220993.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved