An Asymptotic Analysis of Labeled and Unlabeled k-Trees
An Asymptotic Analysis of Labeled and Unlabeled k-Trees
复制标题
DOI：
10.1007/s00453-015-0039-1
复制
发表时间：
2016-08
期刊：
影响因子：
1.1
通讯作者：
M. Drmota;E. Y. Jin
中科院分区：
文献类型：
--
作者：
M. Drmota;E. Y. Jin
在本文中，我们对（随机）k 树的几个形状参数进行了系统的处理。我们的研究是由 k 树在图的树分解和有界树宽度图的背景下的许多重要算法应用推动的。另一方面，从组合的角度来看，k 树也是一个非常有趣的对象。对于标记和未标记的 k 树，我们证明叶子的数量，更一般地说，给定度数的节点数量满足中心极限定理，其平均值和方差在 k 树的大小上呈渐近线性。特别是，我们解决了未标记 k 树的渐近计数问题。通过对生成函数进行适当的奇异性分析，我们表明大小为 n 的未标记 k 树的数量由下式渐近给出，其中 和 表示生成函数的收敛半径。
In this paper we provide a systematic treatment of several shape parameters of (random)k-trees. Our research is motivated by many important algorithmic applications ofk-trees in the context of tree-decomposition of a graph and graphs of bounded tree-width. On the other hand,k-trees are also a very interesting object from the combinatorial point of view. For both labeled and unlabeledk-trees, we prove that the number ofleavesand more generally the number ofnodesof given degree satisfy a central limit theorem with mean value and variance that are asymptotically linear in the size of thek-tree. In particular we solve theasymptotic counting problemfor unlabeledk-trees. By applying a proper singularity analysis of generating functions we show that the numbersof unlabeledk-trees of sizenare asymptotically given by, whereanddenotes the radius of convergence of the generating function.