[Zurück]


Zeitschriftenartikel:

M. Drmota, E. Yu 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 .

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


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s00453-015-0039-1

Elektronische Version der Publikation:
http://download.springer.com/static/pdf/650/art%253A10.1007%252Fs00453-015-0039-1.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Farticle%2F10.1007%2Fs00453-015-0039-1&token2=exp=1452252463~acl=%2Fstatic%2Fpdf%2F650%2Fart%25253A10.1007%25252Fs00453-015-003


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.