Tight conditional lower bounds for longest common increasing subsequence

DOI10.4230/LIPICS.IPEC.2017.15MaRDI QIDQ5111874zbMATHFDO

Authors

Publication date 27 May 2020

zbMATH Keywords

parameterized complexitycombinatorial pattern matchingsequence alignmentsSETHfine-grained complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Tight conditional lower bounds for longest common increasing subsequence
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Faster algorithms for computing longest common increasing subsequences
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• A fast algorithm for computing a longest common increasing subsequence
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear algorithm for 3-letter longest common weakly increasing subsequence
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A simple algorithm for the constrained sequence problems
• A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Algorithms for the Longest Common Subsequence Problem
• An \(O(ND)\) difference algorithm and its variations
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Consequences of Faster Alignment of Sequences
• Constrained LCS: Hardness and Approximation
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Efficient algorithms for finding a longest common increasing subsequence
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast computation of a longest increasing subsequence and application
• Faster algorithms for computing longest common increasing subsequences
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• LCS\(k\): a refined similarity measure
• Multivariate fine-grained complexity of longest common subsequence
• New refinement techniques for longest common subsequence algorithms.
• On computing the length of longest increasing subsequences
• On problems equivalent to \((\min,+)\)-convolution
• On the complexity of \(k\)-SAT
• On the generalized constrained longest common subsequence problems
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Spelling correction in systems programs
• The String-to-String Correction Problem
• The constrained longest common subsequence problem
• The longest common subsequence problem for arc-annotated sequences
• The longest common subsequence problem revisited
• Which problems have strongly exponential complexity?
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?

Cited in

(4)

• Tight conditional lower bounds for longest common increasing subsequence
• Computing the longest common almost-increasing subsequence
• Tighter connections between Formula-SAT and shaving logs
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?

This page was built for publication: Tight conditional lower bounds for longest common increasing subsequence

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