APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD

DOI10.1142/S0129054100000363MaRDI QIDQ4528764zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Gianluca Della Vedova, Giancarlo Mauri, Paola Bonizzoni

Publication date 11 February 2001

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054100000363

zbMATH Keywords

maximum interval weight agreement subtree methodmaximum isomorphic agreement subtree

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1615275
• On the complexity of comparing evolutionary trees
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• scientific article; zbMATH DE number 1833410

Cites work

• An algorithm to find agreement subtrees
• Fast comparison of evolutionary trees
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On approximating the longest path in a graph
• On the agreement of many trees
• On the complexity of comparing evolutionary trees
• On the complexity of constructing evolutionary trees
• Optimization, approximation, and complexity classes
• Proof verification and the hardness of approximation problems
• Sparse Dynamic Programming for Evolutionary-Tree Comparison

Cited in

(3)

• scientific article; zbMATH DE number 1615275 (Why is no real title available?)
• Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species
• On the approximability of the maximum agreement subtree and maximum compatible tree problems

This page was built for publication: APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4528764)