An asymptotic analysis of labeled and unlabeled \(k\)-trees

DOI10.1007/s00453-015-0039-1zbMath1344.05044MaRDI QIDQ308942

Emma Yu Jin, Michael Drmota

Publication date: 6 September 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0039-1

zbMATH Keywords

generating function; central limit theorem; singularity analysis; \(k\)-trees

Mathematics Subject Classification ID

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

05C30: Enumeration in graph theory

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

Related Items

Graph limits of random graphs from a subset of connected k‐trees, On the number of labeled graphs of bounded treewidth, Random enriched trees with applications to random graphs

Cites Work

• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The specification of 2-trees
• Building bridges. Between mathematics and computer science. Selected papers of the conferences held in Budapest, Hungary, August 5--9, 2008 and Keszthely, Hungary, August 11--15, 2008 and other research papers dedicated to László Lovász on the occasion of his 60th birthday
• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The distribution of degrees in a large random tree
• Labelled and unlabelled enumeration of \(k\)-gonal 2-trees
• \(\Gamma \)-species and the enumeration of \(k\)-trees
• The continuum random tree. III
• Counting unlabeled \(k\)-trees
• Enumerating k-trees
• On non-serial dynamic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The number of trees
• Asymptotic Study of Subcritical Graph Classes
• Random Trees
• Limiting Distribution for Distances in k-Trees
• The distribution of nodes of given degree in random trees
• Practical algorithms on partial k-trees with an application to domination-like problems
• On acyclic simplicial complexes
• The number of labeled k-dimensional trees
• The number of labeled k-trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item