Multivariate fine-grained complexity of longest common subsequence
From MaRDI portal
Publication:4607967
zbMATH Open1403.68369arXiv1803.00938MaRDI QIDQ4607967FDOQ4607967
Authors: Karl Bringmann, Marvin Künnemann 
Publication date: 15 March 2018
Full work available at URL: https://arxiv.org/abs/1803.00938
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Cited In (25)
- 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
- A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Longest Common Subsequence with Gap Constraints
- Absent subsequences in words
- Title not available (Why is that?)
- 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
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
- Computing the longest common almost-increasing subsequence
- 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
- Title not available (Why is that?)
- 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)
