concensus string

Hardness results for the center and median string problems under the weighted and unweighted edit distances

Given a finite set of strings, the Median String problem consists in finding a string that minimizes the sum of the edit distances to the strings in the set. Approximations of the median string are used in a very broad range of applications where one …