k median clustering

hi:

i know that k median clustering for strings is NP hard via reduction
from Dominating Set. The edit distance function here in most papers is
defined as D(string1, string2). My question is that is the problem
still NP-hard if the edit does not allow any insertions/deletions but
only one to one comparisons. for instance, if it is simply the hamming
distance between the two strings? Can somebody direct me to a paper
discussing something like this? I could not find it in Compendium of NP
hard problems. google returns mostly experimental papers from gene
matching areas.

thanks.

.

Relevant Pages