On the Largest Common Subtree of Random Leaf-Labeled Binary Trees

DOI10.1137/20M1347504zbMath1483.60009arXiv2006.10545OpenAlexW3036952818MaRDI QIDQ5028357

David J. Aldous

Publication date: 9 February 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

stochastic fragmentationrandom treemaximum agreement subtree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items (2)

Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree ⋮ Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive self-similarity for random trees, random triangulations and Brownian excursion
• Probability theory of classical Euclidean optimization problems
• Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today.
• On the analysis of stochastic divide and conquer algorithms
• Phylogeny
• The Surprising Mathematics of Longest Increasing Subsequences
• Dirichlet and Related Distributions
• Bounds on the Expected Size of the Maximum Agreement Subtree
• Triangulating the Circle, at Random
• Commentary on “Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem” by David Aldous and Persi Diaconis
• Bounds on the Expected Size of the Maximum Agreement Subtree for a Given Tree Shape
• Fragmentation energy

This page was built for publication: On the Largest Common Subtree of Random Leaf-Labeled Binary Trees