- INSTANCE:
set of Characters, for each
, set of states
of character
,
set of species.
- SOLUTION:
A tree
with
- COST FUNCTION:
, where
denotes the Hamming distance [48].
- OBJECTIVE:
Minimize.
*Approx.:*Approximable within approximation ratio for every [4],[65].*Hardness:*NP-hard [48].*Comment:*A phylogeny for a set of n distinct species is a tree whose leaves are all elements of S and where .

2015-04-27 Revision: 288 PDF version