Local search for string problems: brute-force is essentially optimal

DOI10.1016/J.TCS.2013.05.006MaRDI QIDQ2437744zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Danny Hermelin, Christian Komusiewicz

Publication date 13 March 2014

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

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

zbMATH Keywords

closest stringlocal searchlongest common subsequenceparameterized complexityparameterized intractabilityshortest common supersequenceshortest common superstring

Mathematics Subject Classification ID

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

Recommendations

• Local search for string problems: brute force is essentially optimal
• Consequences of Faster Alignment of Sequences
• Maximal common subsequences and minimal common supersequences
• scientific article; zbMATH DE number 827942
• Automata, Languages and Programming

Cites work

• Efficient solutions for the far from most string problem
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• How easy is local search?
• scientific article; zbMATH DE number 1082099 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Lower bounds based on the exponential time hypothesis
• New classes of efficiently solvable generalized traveling salesman problems
• On the hardness of losing weight
• On the parameterized complexity of consensus clustering
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Stable assignment with couples: parameterized complexity and local search
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• The parameterized complexity of local search for TSP, more refined
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(9)

• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• Local search for string problems: brute force is essentially optimal
• String editing under pattern constraints
• Graph clustering problems under the Lens of parameterized local search
• Parameterized local search for vertex cover: when only the search radius is crucial
• Graph clustering problems under the Lens of parameterized local search
• Temporal graph realization with bounded stretch
• Temporal graph realization with bounded stretch
• Fantastic flips and where to find them: a general framework for parameterized local search on partitioning problems

This page was built for publication: Local search for string problems: brute-force is essentially optimal

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