Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

DOI10.1007/978-3-642-02270-8_27zbMath1248.68577MaRDI QIDQ5321718

Binhai Zhu, Lusheng Wang

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02270-8_27

zbMATH Keywords

fixed parameter algorithms; closest string; distinguishing string selection; farthest string

Mathematics Subject Classification ID

68W32: Algorithms on strings

Related Items

Listing Center Strings Under the Edit Distance Metric, Slightly Superexponential Parameterized Problems, Randomized fixed-parameter algorithms for the closest string 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, A heuristic algorithm based on Lagrangian relaxation for the closest string problem, Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem, A combinedgreedy-walkheuristic and simulated annealing approach for the closest string problem

Cites Work

• On covering problems of codes
• On the parameterized intractability of motif search problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distinguishing string selection problems.
• Finding similar regions in many strings
• On the closest string and substring problems
• Closest Substring Problems with Small Distances
• Space and Time Efficient Algorithms for Planted Motif Search
• Genetic Design of Drugs Without Side-Effects
• Fundamentals of Computation Theory