Fixed-parameter algorithms for CLOSEST STRING and related problems
From MaRDI portal
Publication:1424248
DOI10.1007/s00453-003-1028-3zbMath1058.68119MaRDI QIDQ1424248
Rolf Niedermeier, Jens Gramm, 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
68W05: Nonnumerical algorithms
Related Items
Designing and Implementing Algorithms for the Closest String Problem, Unnamed Item, Unnamed Item, Unnamed Item, Tight Hardness Results for Consensus Problems on Circular Strings and Time Series, Parameterized Resiliency Problems via Integer Linear Programming, Efficient Algorithms for the Closest String and Distinguishing String Selection Problems, 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, 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, Separating sets of strings by finding matching patterns is almost always hard, The parameterized complexity of the shared center problem, Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring, Improved optimization modelling for the closest string and related problems, Parameterizing by the number of numbers, Efficient algorithms for consensus string problems minimizing both distance sum and radius, 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, Hardness results for the center and median string problems under the weighted and unweighted edit distances, 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, Parameterized Complexity and Subexponential-Time Computability, What’s Next? Future Directions in Parameterized Complexity, A combinedgreedy-walkheuristic and simulated annealing approach for the closest string problem, Finding Consensus Strings with Small Length Difference Between Input and Solution Strings
