MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

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 ] [ 963 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