Closest Substring Problems with Small Distances

DOI10.1137/060673898MaRDI QIDQ3395036zbMATH OpenOpenAlexFDO

Authors 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

closest substringcomputational complexityconsensus patternfixed-parameter tractabilityparameterized complexity

Mathematics Subject Classification ID

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

Recommendations

• On the parameterized intractability of motif search problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• scientific article; zbMATH DE number 2086391
• More efficient algorithms for closest string and substring problems
• Finding consensus strings with small length difference between input and solution strings

Cited in

(40)

• Fixed-parameter algorithms for CLOSEST STRING and related problems
• On the complexity of finding common approximate substrings.
• On the kernelization complexity of string problems
• Hard problems in similarity searching
• 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
• Randomized fixed-parameter algorithms for the closest string problem
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• Finding similar regions in many strings
• Configurations and minority in the string consensus problem
• What's next? Future directions in parameterized complexity
• On the kernelization complexity of string problems
• Finding consensus strings with small length difference between input and solution strings
• Consensus patterns (probably) has no EPTAS
• The Editor's Corner: Strings, Substrings, and the `Nearest Integer' Function
• On approximating string selection problems with outliers
• A three-string approach to the closest string problem
• scientific article; zbMATH DE number 2081011 (Why is no real title available?)
• Confronting intractability via parameters
• scientific article; zbMATH DE number 2086391 (Why is no real title available?)
• Parameterized complexity analysis for the closest string with wildcards problem
• Finding consensus strings with small length difference between input and solution strings
• Parameterized low-rank binary matrix approximation
• Consensus strings with small maximum distance and small distance sum
• Tight hardness results for consensus problems on circular strings and time series
• The parameterized complexity of the shared center problem
• Combinatorial Pattern Matching
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Listing center strings under the edit distance metric
• Slightly superexponential parameterized problems
• Closest substring problems for regular languages
• Closest substring problems for regular languages
• Parameterized complexity of categorical clustering with size constraints
• Finding a cluster in incomplete data
• Parameterized complexity of feature selection for categorical data clustering
• Average parameterization and partial kernelization for computing medians
• Parameterized complexity of categorical clustering with size constraints
• On the parameterized intractability of motif search problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3395036)