Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

DOI10.1007/978-3-642-02270-8_27MaRDI QIDQ5321718zbMATH OpenOpenAlexFDO

Authors Lusheng Wang, Binhai Zhu

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

closest stringdistinguishing string selectionfarthest stringfixed parameter algorithms

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• More efficient algorithms for closest string and substring problems
• The selective fixing algorithm for the closest string problem
• A recursive exact algorithm for the closest string problem
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Exact algorithm and heuristic for the closest string problem
• Randomized and Parameterized Algorithms for the Closest String Problem
• Algorithms for closest and farthest string problems via rank distance
• Improved LP-based algorithms for the closest string problem
• Randomized fixed-parameter algorithms for the closest string problem

Cites work

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

Cited in

(30)

• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distinguishing string selection problems.
• Efficient solutions for the far from most string problem
• A heuristic algorithm based on Lagrangian relaxation for the closest string problem
• Heuristic approaches to the distinguishing substring selection problem
• String indexing for top-\(k\) close consecutive occurrences
• Algorithms for closest and farthest string problems via rank distance
• Randomized fixed-parameter algorithms for the closest string problem
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• LP-based heuristics for the distinguishing string and substring selection problems
• Optimum Solution of the Closest String Problem via Rank Distance
• A combined greedy-walk heuristic and simulated annealing approach 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
• scientific article; zbMATH DE number 4128413 (Why is no real title available?)
• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• Genetic Design of Drugs Without Side-Effects
• Designing and Implementing Algorithms for the Closest String Problem
• Enumerating Neighbour and Closest Strings
• Parameterized complexity analysis for the closest string with wildcards problem
• Randomized and Parameterized Algorithms for the Closest String Problem
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• The parameterized complexity of the shared center problem
• Listing center strings under the edit distance metric
• Slightly superexponential parameterized problems
• Fundamentals of Computation Theory
• Negative selection algorithms on strings with efficient training and linear-time classification
• Efficient algorithms for consensus string problems minimizing both distance sum and radius

This page was built for publication: Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5321718)