APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD

DOI10.1142/S0129054100000363zbMATH Open0970.68071DBLPjournals/ijfcs/BonizzoniVM00OpenAlexW2021615901WikidataQ57518638 ScholiaQ57518638MaRDI QIDQ4528764FDOQ4528764

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• 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)