article · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2020

Exact and kernelization algorithms for Closet String

Latorre Vilca, Omar

Cited by 0Open access

Abstract

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.

Cite this paper

APA 7

Latorre Vilca, O. (2020). Exact and kernelization algorithms for Closet String. LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas).

MLA 9

Latorre Vilca, Omar. “Exact and kernelization algorithms for Closet String.” LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas), 2020.

Chicago

Latorre Vilca, Omar. 2020. “Exact and kernelization algorithms for Closet String.” LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas).

Harvard

Latorre Vilca, O. (2020) ‘Exact and kernelization algorithms for Closet String’, LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas).

BibTeX

@article{latorrevilca2020exact,
  title = {{Exact and kernelization algorithms for Closet String}},
  author = {Latorre Vilca, Omar},
  journal = {LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas)},
  year = {2020}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.