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_12zbMath1128.05314MaRDI QIDQ4801149

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

Mathematics Subject Classification ID

05C05: Trees

92B10: Taxonomy, cladistics, statistics in mathematical biology

05C85: Graph algorithms (graph-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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