Destruction of recursive trees (Q3154689)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2127740
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Destruction of recursive trees |
scientific article; zbMATH DE number 2127740 |
Statements
14 January 2005
0 references
recursive trees
0 references
removing edges
0 references
0 references
0.8782474
0 references
0.87695235
0 references
0 references
0 references
0.8556303
0 references
0.82279503
0 references
0.82159805
0 references
Destruction of recursive trees (English)
0 references
If a randomly chosen edge is removed from one of the \((n- 1)!\) recursive trees \(T\) with \(n\) labelled vertices, then \(T\) falls into two subtrees one of which contains the root vertex with label 1. Suppose we continue to remove edges from the successively smaller subtrees that contain the root. \textit{A. Meir} and \textit{J. W. Moon} [Math. Biosci. 21, 173--181 (1974; Zbl 0288.05102)] determined the expected number of edges that are removed before the root is isolated and the process stops. The author of the present paper introduces a cost \(c_m= m^\alpha\), \(\alpha\geq 0\), associated with removing an edge from a recursive tree with \(m\) vertices. He considers the procedure just described and a related procedure in which the edge-removing process is applied to all subtrees encountered and terminates when all edges have been removed. He determines the asymptotic behaviour of the \(s\)th moment and the \(s\)th centered moment of the total costs incurred before these two processes terminate, for any fixed positive integer \(s\). In particular, the expected value of the total cost for both procedures is asymptotic to \(n^{\alpha+ 1}/(\alpha+ 1)\log n\), where we assume that \(\alpha> 0\) in the case of the second procedure. For the entire collection see [Zbl 1047.68003].
0 references