TY - JOUR
AU - Latorre Vilca, Omar
PY - 2020/12/25
Y2 - 2024/11/05
TI - Exact and kernelization algorithms for Closet String
JF - Selecciones Matemáticas
JA - Sel.Mat.
VL - 7
IS - 02
SE -
DO - 10.17268/sel.mat.2020.02.08
UR - https://revistas.unitru.edu.pe/index.php/SSMM/article/view/3080
SP - 257-266
AB - <p>In this paper we address CLOSEST STRING problem that arises in web searching, coding theory and computational molecular biology. To solve it is to find a string that minimizes the maximum Hamming distance from a given set of strings. CLOSEST STRING is an NP-hard problem. This paper proposes two linear-time algorithms, one for the general case, a kernelization algorithm, and the other for three-strings, a linear-time algorithm called Minimization First Algorithm (MFA). A formal proof of the correctness and the computational complexity of the proposed algorithms are given.</p>
ER -