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

      0 references
      14 January 2005
      0 references
      recursive trees
      0 references
      removing edges
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references