M. Drmota, Y. Jin:
"An Asymptotic Analysis of Labeled and Unlabeled k-Trees";
Algorithmica (online), -- (2015), online; 27 S.

Kurzfassung englisch:
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 of k-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 unlabeled k-trees, we prove that the number of leaves and more generally the number of nodes of given degree satisfy a central limit theorem with mean value and variance that are asymptotically linear in the size of the k-tree. In particular we solve the asymptotic counting problem for unlabeled k-trees. By applying a proper singularity analysis of generating functions we show that the numbers U k (n) of unlabeled k-trees of size n are asymptotically given by U k (n)∼c k n −5/2 ρ −n k , where c k >0 and ρ k >0 denotes the radius of convergence of the generating function U(z)=∑ n≥0 U k (n)z n .

k-trees; Generating function; Singularity analysis; Central limit theorem

"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)

Elektronische Version der Publikation:

Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.