Parameterized complexity analysis for the closest string with wildcards problem

DOI10.1016/J.TCS.2015.06.043zbMATH Open1329.68143OpenAlexW2180648128MaRDI QIDQ495996FDOQ495996

Authors: Danny Hermelin, Liat Rozenberg 

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.043

Recommendations

• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• Randomized and Parameterized Algorithms for the Closest String Problem
• Randomized fixed-parameter algorithms for the closest string problem
• scientific article; zbMATH DE number 2086391
• On the kernelization complexity of string problems

zbMATH Keywords

computational biologyfixed-parameter algorithmsclosest string problemparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Cites Work

• Reducibility among combinatorial problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• On the closest string and substring problems
• Closest Substring Problems with Small Distances
• More efficient algorithms for closest string and substring problems
• A three-string approach to the closest string problem
• A linear-time algorithm for the 1-mismatch problem
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Title not available (Why is that?)
• On covering problems of codes
• On the parameterized intractability of motif search problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Title not available (Why is that?)
• A closer look at the closest string and closest substring problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial and APX-hard cases of the individual haplotyping problem
• A dynamic programming algorithm for the \(k\)-haplotyping problem
• Haplotype assembly from aligned weighted SNP fragments
• Title not available (Why is that?)
• An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs

Cited In (8)

• Randomized and Parameterized Algorithms for the Closest String Problem
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• On the parameterized complexity of clustering problems for incomplete data
• Separating sets of strings by finding matching patterns is almost always hard
• The complexity of binary matrix completion under diameter constraints
• Parameterized lower bound and inapproximability of polylogarithmic string barcoding
• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial \(n\)-fold integer programming and applications

Uses Software

• HapCUT

This page was built for publication: Parameterized complexity analysis for the closest string with wildcards problem

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