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

consensus word analysisexact algorithms

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

(66)

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

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)