The Wiener index of random trees

被引：37

作者：

Neininger, R ^{[1
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ H3A 2K6, Canada

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2002年 / 11卷 / 06期

关键词：

D O I：

10.1017/S0963548302005321

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Wiener index is analysed for random recursive trees and random binary search trees in uniform probabilistic models. We obtain expectations, asymptotics for the variances, and limit laws for this parameter. The limit distributions are characterized as the projections of bivariate measures that satisfy certain fixed point equations. Covariances, asymptotic correlations, and bivariate limit laws for the Wiener index and the internal path length are given.

引用

页码：587 / 597

页数：11

共 16 条

[1]

Chern HH, 2001, ALGORITHMICA, V29, P44, DOI 10.1007/s004530010054

[2] On the distribution of distances in recursive trees [J].

Dobrow, RP .

JOURNAL OF APPLIED PROBABILITY, 1996, 33 (03) :749-757

[3] Total path length for random recursive trees [J].

Dobrow, RP ;

Fill, JA .

COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (04) :317-333

[4]

Dobrynin AA, 1999, COMPUT CHEM, V23, P571, DOI 10.1016/S0097-8485(99)00035-2

[5] The average wiener index of trees and chemical trees [J].

Dobrynin, AA ;

Gutman, I .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1999, 39 (04) :679-683

[6] Wiener index of trees: Theory and applications [J].

Dobrynin, AA ;

Entringer, R ;

Gutman, I .

ACTA APPLICANDAE MATHEMATICAE, 2001, 66 (03) :211-249

[7]

Entringer R., 1994, AUSTRALAS J COMB, V10, P211, DOI DOI 10.1023/A:1010767517079

[8] HYPERGEOMETRICS AND THE COST-STRUCTURE OF QUADTREES [J].

FLAJOLET, P ;

LABELLE, G ;

LAFOREST, L ;

SALVY, B .

RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (02) :117-144

[9]

Mahmoud H., 1991, PROBAB ENG INFORM SC, V5, P53

[10] On a multivariate contraction method for random recursive structures with applications to quicksort [J].

Neininger, R .

RANDOM STRUCTURES & ALGORITHMS, 2001, 19 (3-4) :498-524

← 1 2 →