Sparse Dynamic Programming for Evolutionary-Tree Comparison

DOI10.1137/S0097539794262422zbMath0871.05050MaRDI QIDQ4337441

Martin Farach, Mikkel Thorup

Publication date: 24 September 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

comparisondynamic programmingrooted treeevolutionary treeunary weighted bipartite matching

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) General biology and biomathematics (92B05)

Related Items

APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD ⋮ Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species ⋮ Improved algorithms for maximum agreement and compatible supertrees ⋮ Computing the maximum agreement of phylogenetic networks ⋮ An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation ⋮ On the complexity of comparing evolutionary trees ⋮ An improved algorithm for the maximum agreement subtree problem