Distinct fringe subtrees in random trees

DOI10.1007/S00453-022-01013-YOpenAlexW3163691089MaRDI QIDQ2105315FDOQ2105315

Authors: Yanyan Li 

Publication date: 8 December 2022

Published in: Algorithmica (Search for Journal in Brave)

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

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

zbMATH Keywords

tree compressionsimply generated treesincreasing treesfringe subtrees

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Distinct Fringe Subtrees in Random Trees
• 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

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)