A General Central Limit Theorem for Shape Parameters of m-ary Tries and PATRICIA Tries

檔案

本條目沒有附加檔案。

日期

2014-03-24

類型

期刊名稱

ELECTRONIC JOURNAL OF COMBINATORICS

卷期與頁次

第 21 卷第 1 期

ISSN

1077-8926

語言

英文

摘要

Tries and PATRICIA tries are fundamental data structures in computer science with numerous applications. In a recent paper, a general framework for obtaining the mean and variance of additive shape parameters of tries and PATRICIA tries under the Bernoulli model was proposed. In this note, we show that a slight modification of this framework yields a central limit theorem for shape parameters, too. This central limit theorem contains many of the previous central limit theorems from the literature and it can be used to prove recent conjectures and derive new results. As an example, we will consider a refinement of the size of tries and PATRICIA tries, namely, the number of nodes of fixed outdegree and obtain (univariate and bivariate) central limit theorems. Moreover, trivariate central limit theorems for size, internal path length and internal Wiener index of tries and PATRICIA tries are derived as well.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Fuchs, M., & Lee, C.-K. (2014). A General Central Limit Theorem for Shape Parameters of m-ary Tries and PATRICIA Tries. ELECTRONIC JOURNAL OF COMBINATORICS, 21(1). https://ir.lib.nycu.edu.tw/handle/11536/23971

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/23971