Multivariate fine-grained complexity of longest common subsequence
From MaRDI portal
Publication:4607967
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
(45)- FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Computing the longest common almost-increasing subsequence
- Tight conditional lower bounds for longest common increasing subsequence
- The complexity of binary matrix completion under diameter constraints
- Absent subsequences in words
- Tighter connections between Formula-SAT and shaving logs
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Scattered Factor-Universality of Words
- Sketching, streaming, and fine-grained complexity of (weighted) LCS
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- Tight conditional lower bounds for longest common increasing subsequence
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
- 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
- Linear-space S-table algorithms for the longest common subsequence problem
- Longest Common Subsequence with Gap Constraints
- Subsequences in bounded ranges: matching and analysis problems
- Existential Definability over the Subword Ordering
- Combinatorial algorithms for subsequence matching: a survey
- A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
- Algorithms and hardness for the longest common subsequence of three strings and related problems
- Jumbled scattered factors
- A space-efficient algorithm for longest common almost increasing subsequence of two sequences
- Subsequences with generalised gap constraints: upper and lower complexity bounds
- Hairpin completion distance lower bound
- Approximating the geometric knapsack problem in near-linear time and dynamically
- k-universality of regular languages revisited
- The edit distance to k-subsequence universality
- Longest common subsequence with gap constraints
- The longest common subsequence problem for small alphabets in the word RAM model
- The edit distance to \(k\)-subsequence universality
- Efficiently testing Simon's congruence
- Binary matrix completion under diameter constraints
- Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation
- Fine-grained hardness for edit distance to a fixed sequence
- Improved approximation for longest common subsequence over small alphabets
- A linear-time \(n^{0.4}\)-approximation for longest common subsequence
- Streaming and small space approximation algorithms for edit distance and longest common subsequence
- Longest common substring with gaps and related problems
- Scattered factor universality -- a survey
- Thermodynamical approach to the longest common subsequence problem
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)
