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 treesConference paper
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 so-called 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 non-negative integer.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)