On the approximability of the maximum agreement subtree and maximum compatible tree problems
DOI10.1016/j.dam.2008.06.007zbMath1190.68081OpenAlexW2046397190MaRDI QIDQ1028128
Christophe Paul, François Nicolas, Sylvain Guillemot, Vincent Berry
Publication date: 30 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.007
approximation algorithmcomputational biologymaximum independent setphylogeneticsapproximation hardnessmaximum agreement subtreeminimum dominating setcomplement problemconsensus treemaximum compatible treemaximum refinement subtreemaximum star-forest
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Correlation clustering
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Some simplified NP-complete graph problems
- Kaikoura tree theorems: Computing the maximum agreement subtree
- Star forests, dominating sets and Ramsey-type problems
- On the agreement of many trees
- Finding similar regions in many sequences
- Extension operations on sets of leaf-labelled trees
- Finding a maximum compatible tree is NP-hard for sequences and trees
- Tree-edges deletion problems with bounded diameter obstruction sets
- Parametrized complexity theory.
- Clustering with qualitative information
- An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
- Algorithmic construction of sets for k -restrictions
- Improved Approximation Algorithms for the Spanning Star Forest Problem
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Approximation algorithms for NP-complete problems on planar graphs
- Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
- Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
- Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees
- Combinatorial Pattern Matching
- Algorithms – ESA 2004
- Computing and Combinatorics
- Combinatorial optimization. Theory and algorithms.
- On the complexity of comparing evolutionary trees
This page was built for publication: On the approximability of the maximum agreement subtree and maximum compatible tree problems
