Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

The total Steiner $k$-distance for $b$-ary recursive trees and linear recursive trees

Abstract : 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.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:32:46 PM
Last modification on : Tuesday, March 7, 2017 - 3:07:23 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:49:55 AM


Publisher files allowed on an open archive




Götz Olaf Munsonius. The total Steiner $k$-distance for $b$-ary recursive trees and linear recursive trees. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.527-548, ⟨10.46298/dmtcs.2779⟩. ⟨hal-01185577⟩



Record views


Files downloads