Fixed-parameter algorithms for CLOSEST STRING and related problems

DOI10.1007/S00453-003-1028-3MaRDI QIDQ1424248zbMATH OpenOpenAlexFDO

Authors Jens Gramm, Rolf Niedermeier, Peter Rossmanith

Publication date 11 March 2004

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-003-1028-3

zbMATH Keywords

exact algorithmsconsensus word analysis

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 2081011
• Closest Substring Problems with Small Distances
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Randomized fixed-parameter algorithms for the closest string problem
• On the closest string and substring problems

Cited in

(58)

• Designing and Implementing Algorithms for the Closest String Problem
• The bounded search tree algorithm for the closest string problem has quadratic smoothed complexity
• Consensus string problem for multiple regular languages
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• Combinatorial \(n\)-fold integer programming and applications
• Randomized and Parameterized Algorithms for the Closest String Problem
• A three-string approach to the closest string problem
• Listing center strings under the edit distance metric
• Local search for string problems: brute-force is essentially optimal
• Combinatorial \(n\)-fold integer programming and applications
• Parameterized complexity analysis for the closest string with wildcards problem
• Consensus string problem for multiple regular languages
• On approximating string selection problems with outliers
• Slightly superexponential parameterized problems
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• Finding consensus strings with small length difference between input and solution strings
• scientific article; zbMATH DE number 2081011 (Why is no real title available?)
• Parameterized resiliency problems
• On the parameterized intractability of motif search problems
• A heuristic algorithm based on Lagrangian relaxation for the closest string problem
• A parallel multistart algorithm for the closest string problem
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• A GRASP algorithm for the closest string problem using a probability-based heuristic
• On the parameterized complexity of clustering problems for incomplete data
• A three-string approach to the closest string problem
• scientific article; zbMATH DE number 7525465 (Why is no real title available?)
• Parameterized enumeration for modification problems
• On the kernelization complexity of string problems
• Designing and implementing algorithms for the closest string problem
• On the kernelization complexity of string problems
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• On the hardness of the consensus string problem
• Parameterized resiliency problems via integer linear programming
• On the computational complexity of closest genome problems
• scientific article; zbMATH DE number 2086391 (Why is no real title available?)
• A combined greedy-walk heuristic and simulated annealing approach for the closest string problem
• On a cyclic string-to-string correction problem
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Configurations and minority in the string consensus problem
• Parameterized complexity and subexponential-time computability
• Tight hardness results for consensus problems on circular strings and time series
• Optimum Solution of the Closest String Problem via Rank Distance
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Consensus strings with small maximum distance and small distance sum
• On the hardness of maximum rank aggregation problems
• On the string consensus problem and the Manhattan sequence consensus problem
• Randomized fixed-parameter algorithms for the closest string problem
• Separating sets of strings by finding matching patterns is almost always hard
• The complexity of binary matrix completion under diameter constraints
• Improved optimization modelling for the closest string and related problems
• Consensus strings with small maximum distance and small distance sum
• What's next? Future directions in parameterized complexity
• Configurations and minority in the string consensus problem
• The parameterized complexity of the shared center problem
• Closest Substring Problems with Small Distances

This page was built for publication: Fixed-parameter algorithms for CLOSEST STRING and related problems

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