Bounds on the Expected Size of the Maximum Agreement Subtree

DOI10.1137/140997750zbMath1323.05033arXiv1411.7338OpenAlexW2963271684WikidataQ57439218 ScholiaQ57439218MaRDI QIDQ3449864

Katherine St. John, Seth Sullivant, Lam Si Tung Ho, Colby Long, Daniel Irving Bernstein, Mike A. Steel

Publication date: 30 October 2015

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

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

zbMATH Keywords

random treesYule-Harding distributionagreement subtrees

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (10)

Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree ⋮ Exchangeable and sampling-consistent distributions on rooted binary trees ⋮ Inducibility in Binary Trees and Crossings in Random Tanglegrams ⋮ Extremal distances for subtree transfer operations in binary trees ⋮ Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees ⋮ On the extremal maximum agreement subtree problem ⋮ Counting Markov equivalence classes for DAG models on trees ⋮ Bounds on the Expected Size of the Maximum Agreement Subtree for a Given Tree Shape ⋮ On the Largest Common Subtree of Random Leaf-Labeled Binary Trees ⋮ On the Maximum Agreement Subtree Conjecture for Balanced Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Kaikoura tree theorems: Computing the maximum agreement subtree
• The maximum agreement subtree problem
• On the Distribution of Lengths of Evolutionary Trees
• Polya Urn Models
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• The probabilities of rooted tree-shapes generated by random bifurcation

This page was built for publication: Bounds on the Expected Size of the Maximum Agreement Subtree