Fixed-parameter algorithms for CLOSEST STRING and related problems
From MaRDI portal
Publication:1424248
DOI10.1007/s00453-003-1028-3zbMath1058.68119OpenAlexW1979149941MaRDI 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
Related Items (46)
Parameterized Resiliency Problems via Integer Linear Programming ⋮ Configurations and minority in the string consensus problem ⋮ 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 ⋮ Efficient Algorithms for the Closest String and Distinguishing String Selection Problems ⋮ 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 ⋮ Finding Consensus Strings with Small Length Difference Between Input and Solution Strings ⋮ On approximating string selection problems with outliers ⋮ On the hardness of the consensus string problem ⋮ The complexity of binary matrix completion under diameter constraints ⋮ A three-string approach to the closest string problem ⋮ On the string consensus problem and the Manhattan sequence consensus problem ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Unnamed Item ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Local search for string problems: brute-force is essentially optimal ⋮ Tight Hardness Results for Consensus Problems on Circular Strings and Time Series ⋮ Improved optimization modelling for the closest string and related problems ⋮ Designing and Implementing Algorithms for the Closest String Problem ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Parameterized complexity analysis for the closest string with wildcards problem ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ On the kernelization complexity of string problems ⋮ The parameterized complexity of the shared center problem ⋮ Parameterizing by the number of numbers ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ 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 ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Unnamed Item ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ Slightly Superexponential Parameterized Problems ⋮ On the hardness of maximum rank aggregation problems ⋮ Efficient algorithms for consensus string problems minimizing both distance sum and radius ⋮ Parameterized Enumeration for Modification Problems ⋮ Consensus string problem for multiple regular languages ⋮ Unnamed Item ⋮ 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 ⋮ 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
This page was built for publication: Fixed-parameter algorithms for CLOSEST STRING and related problems
