Distinct fringe subtrees in random trees

DOI10.1007/S00453-022-01013-YMaRDI QIDQ2105315zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 8 December 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2105.04231

zbMATH Keywords

tree compressionsimply generated treesincreasing treesfringe subtrees

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• On the collection of fringe subtrees in random binary trees
• Repeated fringe subtrees in random rooted trees
• Protected nodes and fringe subtrees in some random trees
• Asymptotic fringe distributions for general families of random trees
• On the distribution of subtree orders of a tree

Cites work

• scientific article; zbMATH DE number 5344975 (Why is no real title available?)
• scientific article; zbMATH DE number 3978019 (Why is no real title available?)
• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• A Universal Grammar-Based Code for Lossless Compression of Binary Trees
• A central limit theorem for additive functionals of increasing trees
• A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees
• Analytic combinatorics
• Asymptotic fringe distributions for general families of random trees
• Average case analysis of leaf-centric binary tree sources
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• Compression of unordered XML trees
• Generating linear extensions of posets by transpositions
• Highly expressive query languages for unordered data trees
• Isomorphism and symmetries in random phylogenetic trees
• Level of nodes in increasing trees revisited
• Limit theorems for subtree size profiles of increasing trees
• Limiting distributions for additive functionals on Catalan trees
• Linear unification
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• On the Altitude of Nodes in Random Trees
• On the collection of fringe subtrees in random binary trees
• On the richness of the collection of subtrees in random binary search trees
• On the subtree size profile of binary search trees
• On the variety of shapes on the fringe of a random recursive tree
• Probability: A Graduate Course
• Protected nodes and fringe subtrees in some random trees
• Random Trees
• Random cutting and records in deterministic and random trees
• Repeated fringe subtrees in random rooted trees
• Schemas for unordered XML on a DIME
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• The number of trees
• Universal Tree Source Coding Using Grammar-Based Compression
• XML compression via directed acyclic graphs

Cited in

(4)

• On the shape of the fringe of various types of random trees
• Sub-trees of a random tree
• Non-fringe subtrees in conditioned Galton-Watson trees
• Distinct Fringe Subtrees in Random Trees

This page was built for publication: Distinct fringe subtrees in random trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105315)