Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

  • 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)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: internal path length,Wiener index,total Steiner k-distance,recursive trees,contraction method,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

Consultation statistics

This page has been seen 341 times.
This article's PDF has been downloaded 367 times.