Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
On the Efficiency of the Hamming C-Centerstring Problems
verfasst von : Amihood Amir, Jessica Ficler, Liam Roditty, Oren Sar Shalom
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
Consensus String Problem
is that of finding a string, such that the maximum Hamming distance from it to a given set of strings of the same length is minimized. However, a generalization is necessary for clustering. One needs to consider a partition into a number of sets, each with a distinct centerstring. In this paper we define two natural versions of the consensus problem for c centerstrings. We analyse the hardness and fixed parameter tractability of these problems and provide approximation algorithms.