Article ID Journal Published Year Pages File Type
10331346 Information Processing Letters 2005 6 Pages PDF
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
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Approximating the Maximum Agreement Forest on k trees
Authors
,