Exact and kernelization algorithms for Closet String
Copyright policy )Exact and kernelization algorithms for Closet String
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.
closest string problem, T57-57.97, Applied mathematics. Quantitative methods, Algoritmo de parámetro fijo, Closest String Problem, Optimización combinatoria, exact algorithm, Exact Algorithm, Fixed Parameter Algorithm, Kernelización, Combinatorial Optimization, Algoritmo exacto, fixed parameter algorithm, kernelization, QA1-939, Kernelization, Problema de la subsecuencia de caracteres más próxima, combinatorial optimization, Mathematics
closest string problem, T57-57.97, Applied mathematics. Quantitative methods, Algoritmo de parámetro fijo, Closest String Problem, Optimización combinatoria, exact algorithm, Exact Algorithm, Fixed Parameter Algorithm, Kernelización, Combinatorial Optimization, Algoritmo exacto, fixed parameter algorithm, kernelization, QA1-939, Kernelization, Problema de la subsecuencia de caracteres más próxima, combinatorial optimization, Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!