Closest Substring Problems with Small Distances

DOI10.1137/060673898zbMath1178.68695OpenAlexW2019404372MaRDI QIDQ3395036

Dániel Marx

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

zbMATH Keywords

computational complexityfixed-parameter tractabilityparameterized complexityclosest substringconsensus pattern

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (24)

Parameterized complexity of categorical clustering with size constraints ⋮ Consensus Patterns (Probably) Has no EPTAS ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Efficient Algorithms for the Closest String and Distinguishing String Selection Problems ⋮ 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 ⋮ A three-string approach to the closest string problem ⋮ Unnamed Item ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Tight Hardness Results for Consensus Problems on Circular Strings and Time Series ⋮ Parameterized low-rank binary matrix approximation ⋮ Confronting intractability via parameters ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Parameterized complexity analysis for the closest string with wildcards problem ⋮ On the kernelization complexity of string problems ⋮ The parameterized complexity of the shared center problem ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ Slightly Superexponential Parameterized Problems ⋮ Average parameterization and partial kernelization for computing medians ⋮ Consensus strings with small maximum distance and small distance sum ⋮ Randomized fixed-parameter algorithms for the closest string problem

This page was built for publication: Closest Substring Problems with Small Distances