Back to Search
Start Over
Exact and kernelization algorithms for Closet String
- Source :
- Selecciones Matemáticas, Vol 7, Iss 02, Pp 257-266 (2020)
- Publication Year :
- 2020
- Publisher :
- Universidad Nacional de Trujillo, 2020.
-
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.
Details
- Language :
- Spanish; Castilian
- ISSN :
- 24111783
- Volume :
- 7
- Issue :
- 02
- Database :
- Directory of Open Access Journals
- Journal :
- Selecciones Matemáticas
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.ff3d2326a53c4c2fb311435969b31b44
- Document Type :
- article
- Full Text :
- https://doi.org/10.17268/sel.mat.2020.02.08