uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Long and short paths in uniform random recursive dags
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2011 (English)In: Arkiv för matematik, ISSN 0004-2080, E-ISSN 1871-2487, Vol. 49, no 1, 61-77 p.Article in journal (Refereed) Published
Abstract [en]

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 sigma such that S (n) /log n ->sigma in probability as n -> a. We also show that max (1a parts per thousand currency signia parts per thousand currency signn) S (i) /log n ->sigma in probability.

Place, publisher, year, edition, pages
2011. Vol. 49, no 1, 61-77 p.
National Category
URN: urn:nbn:se:uu:diva-150683DOI: 10.1007/s11512-009-0118-0ISI: 000288019500004OAI: oai:DiVA.org:uu-150683DiVA: diva2:408243
Available from: 2011-04-04 Created: 2011-04-04 Last updated: 2011-04-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Analysis and Applied Mathematics
In the same journal
Arkiv för matematik

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 155 hits
ReferencesLink to record
Permanent link

Direct link