scientific article; zbMATH DE number 7205199

DOI10.4230/LIPIcs.IPEC.2017.15zbMath1443.68068MaRDI QIDQ5111874

No author found.

Publication date: 27 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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)

Related Items (2)

Computing the longest common almost-increasing subsequence ⋮ Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?

Cites Work

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

This page was built for publication: