Alois Panholzer - Analysis of some parameters for random nodes in priority trees

dmtcs:447 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 2 -
Analysis of some parameters for random nodes in priority trees

Authors: Alois Panholzer 1

  • 1 Institut für Diskrete Mathematik und Geometrie [Wien]

Priority trees are a certain data structure used for priority queue administration. Under the model that all permutations of the numbers 1, . . . , n are equally likely to construct a priority tree of size n we study the following parameters in size-n trees: depth of a random node, number of right edges to a random node, and number of descendants of a random node. For all parameters studied we give limiting distribution results.

Volume: Vol. 10 no. 2
Section: Analysis of Algorithms
Published on: January 1, 2008
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1214/ejp.v16-885
  • 10.1214/ejp.v16-885
On the Moment-Transfer Approach for Random Variables Satisfying a One-Sided Distributional Recurrence

1 Document citing this article

Consultation statistics

This page has been seen 226 times.
This article's PDF has been downloaded 199 times.