Multivariate fine-grained complexity of longest common subsequence

MaRDI QIDQ4607967zbMATH OpenFDO

Authors Karl Bringmann, Marvin Künnemann

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1803.00938, http://dl.acm.org/citation.cfm?id=3175349

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)

Recommendations

• The longest common subsequence problem revisited
• Lower Bounds and Parameterized Approach for Longest Common Subsequence
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Fast linear-space computations of longest common subsequences

Cited in

(26)

• Tight conditional lower bounds for longest common increasing subsequence
• Tight conditional lower bounds for longest common increasing subsequence
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Tighter connections between Formula-SAT and shaving logs
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Longest Common Subsequence with Gap Constraints
• Absent subsequences in words
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Linear-space S-table algorithms for the longest common subsequence problem
• Subsequences in bounded ranges: matching and analysis problems
• Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
• Existential Definability over the Subword Ordering
• Computing the longest common almost-increasing subsequence
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Absent Subsequences in Words
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• Scattered Factor-Universality of Words
• Combinatorial algorithms for subsequence matching: a survey
• FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
• Thermodynamical approach to the longest common subsequence problem
• The complexity of binary matrix completion under diameter constraints
• Algorithms and hardness for the longest common subsequence of three strings and related problems

This page was built for publication: Multivariate fine-grained complexity of longest common subsequence

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