Götz Olaf Munsonius

The total Steiner $k$distance for $b$ary recursive trees and linear recursive trees
dmtcs:2779 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

https://doi.org/10.46298/dmtcs.2779
The total Steiner $k$distance for $b$ary recursive trees and linear recursive trees
Authors: Götz Olaf Munsonius ^{1}
NULL
Götz Olaf Munsonius
1 Department for Mathematics and Computer Science
We prove a limit theorem for the total Steiner $k$distance of a random $b$ary recursive tree with weighted edges. The total Steiner $k$distance is the sum of all Steiner $k$distances in a tree and it generalises the Wiener index. The limit theorem is obtained by using a limit theorem in the general setting of the contraction method. In order to use the contraction method we prove a recursion formula and determine the asymptotic expansion of the expectation using the socalled Master Theorem by Roura (2001). In a second step we prove a transformation of the total Steiner $k$distance of $b$ary trees with weighted edges to arbitrary recursive trees. This transformation yields the limit theorem for the total Steiner $k$distance of the linear recursive trees when the parameter of these trees is a nonnegative integer.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)