Approximating the Maximum Agreement Forest on k trees |
| |
| Authors: | Fré dé ric Chataigner |
| |
| Affiliation: | LIAFA, université Denis Diderot, 2 place Jussieu, Paris cedex 05 75251, France |
| |
| Abstract: | The Maximum Agreement Forest problem (MAF) asks for the largest common subforest of a set of binary trees. This problem is known to be MAXSNP-complete for instances consisting of 2 trees. We show that it remains MAXSNP-complete for k?2 trees. |
| |
| Keywords: | Computational complexity Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
