Closest Substring Problems with Small Distances
From MaRDI portal
Publication:3395036
DOI10.1137/060673898zbMath1178.68695MaRDI QIDQ3395036
Publication date: 20 August 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/be61dd2f7b8fa9d909120d741889f90780682cea
computational complexity; fixed-parameter tractability; parameterized complexity; closest substring; consensus pattern
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W32: Algorithms on strings
Related Items
Unnamed Item, Tight Hardness Results for Consensus Problems on Circular Strings and Time Series, Parameterized Low-Rank Binary Matrix Approximation, Efficient Algorithms for the Closest String and Distinguishing String Selection Problems, Listing Center Strings Under the Edit Distance Metric, Slightly Superexponential Parameterized Problems, Parameterized complexity of categorical clustering with size constraints, Randomized fixed-parameter algorithms for the closest string problem, On approximating string selection problems with outliers, A three-string approach to the closest string problem, Confronting intractability via parameters, Parameterized complexity analysis for the closest string with wildcards problem, The parameterized complexity of the shared center problem, Average parameterization and partial kernelization for computing medians, Parameterized complexity of categorical clustering with size constraints, On the kernelization complexity of string problems, Combinatorial \(n\)-fold integer programming and applications, Parameterized low-rank binary matrix approximation, Parameterized \(k\)-clustering: tractability island, Consensus strings with small maximum distance and small distance sum, Polynomial time approximation schemes for all 1-center problems on metric rational set similarities, What’s Next? Future Directions in Parameterized Complexity, Finding Consensus Strings with Small Length Difference Between Input and Solution Strings, Consensus Patterns (Probably) Has no EPTAS
