[Zurück]


Beiträge in Tagungsbänden:

Y. Jin, M. Drmota:
"Scaling limit of random k-trees";
in: "2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)", 1; herausgegeben von: SIAM; Society for Industrial and Applied Mathematics, 2016, ISBN: 978-1-61197-432-4, S. 56 - 65.



Kurzfassung englisch:
We consider a random k-tree Gn,k that is uniformly selected from the class of labelled k-trees with n + k vertices. Since 1-trees are just trees, it is well-known that Gn,1 (after scaling the distances by converges to the Continuum Random Tree Our main result is that for k ≠ 1, the random k-tree Gn,k, scaled by where Hk-1 is the (k - 1)-th Harmonic number, converges to the Continuum Random Tree too. In particular this shows that the diameter as well as the typical distance of two vertices in a random k-tree Gn,k are of order


Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611974324.7


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1137/1.9781611974324.7


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.