An improved algorithm for the maximum agreement subtree problem

DOI10.1016/j.ipl.2005.02.005zbMath1182.68368OpenAlexW2073976071MaRDI QIDQ1041753

Maw-Shang Chang, Ling-Ju Hung, Chia-Ben Shen, Chuan-Min Lee, Chuan Yi Tang

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.02.005

zbMATH Keywords

design of algorithmsevolutionary treemaximum agreement subtreemultidimensional binary search treeleaf-labeled treemultidimensional range search tree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species, Constructing the R* consensus tree of two trees in subcubic time, Comparing and aggregating partially resolved trees, An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation, Faster algorithms for computing the R* consensus tree

Cites Work

• Unnamed Item
• Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
• Kaikoura tree theorems: Computing the maximum agreement subtree
• On the agreement of many trees
• An algorithm to find agreement subtrees
• Fast comparison of evolutionary trees
• An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
• Multidimensional Binary Search Trees in Database Applications
• Tree Contractions and Evolutionary Trees
• Sparse Dynamic Programming for Evolutionary-Tree Comparison
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Computing the agreement of trees with bounded degrees