More Efficient Algorithms for Closest String and Substring Problems

DOI10.1137/080739069zbMath1206.68377MaRDI QIDQ3586187

Xiaoming Sun, Bin Ma

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080739069

zbMATH Keywords

approximation algorithms; fixed-parameter algorithm; closest string; closest substring

Mathematics Subject Classification ID

68W32: Algorithms on strings

Related Items

Designing and Implementing Algorithms for the Closest String Problem, Unnamed Item, Consensus String Problem for Multiple Regular Languages, Listing Center Strings Under the Edit Distance Metric, Slightly Superexponential Parameterized Problems, Closest substring problems for regular languages, The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance, Low-Rank Binary Matrix Approximation in Column-Sum Norm., Randomized fixed-parameter algorithms for the closest string problem, Configurations and minority in the string consensus problem, On approximating string selection problems with outliers, On the hardness of the consensus string problem, A three-string approach to the closest string problem, Parameterized complexity analysis for the closest string with wildcards problem, The parameterized complexity of the shared center problem, On the string consensus problem and the Manhattan sequence consensus problem, Consensus string problem for multiple regular languages, Combinatorial \(n\)-fold integer programming and applications, Designing and implementing algorithms for the closest string problem, Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem, Polynomial time approximation schemes for all 1-center problems on metric rational set similarities, What’s Next? Future Directions in Parameterized Complexity