Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time

DOI10.1007/3-540-44696-6_12zbMATH Open1128.05314OpenAlexW1527979405MaRDI QIDQ4801149FDOQ4801149

Authors: Ganeshkumar Ganapathysaravanabavan, Tandy J. Warnow 

Publication date: 6 April 2003

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-44696-6_12

Recommendations

• Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees
• scientific article; zbMATH DE number 1947052
• Compatibility of unrooted phylogenetic trees is FPT
• Combinatorial Pattern Matching
• Fast compatibility testing for rooted phylogenetic trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Taxonomy, cladistics, statistics in mathematical biology (92B10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (3)

• Maximum agreement and compatible supertrees
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• Improved algorithms for maximum agreement and compatible supertrees

This page was built for publication: Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time

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