APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD

DOI10.1142/S0129054100000363zbMath0970.68071OpenAlexW2021615901WikidataQ57518638 ScholiaQ57518638MaRDI QIDQ4528764

Giancarlo Mauri, Gianluca Della Vedova, 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)

Related Items (1)

On the approximability of the maximum agreement subtree and maximum compatible tree problems

Cites Work

• On approximating the longest path in a graph
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Optimization, approximation, and complexity classes
• On the complexity of constructing evolutionary 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
• Proof verification and the hardness of approximation problems
• Sparse Dynamic Programming for Evolutionary-Tree Comparison
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• On the complexity of comparing evolutionary trees

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