Tight conditional lower bounds for longest common increasing subsequence (Q2272597)

scientific article

Language	Label	Description	Also known as
English	Tight conditional lower bounds for longest common increasing subsequence	scientific article

Statements

instance of

scholarly article

0 references

title

Tight conditional lower bounds for longest common increasing subsequence (English)

0 references

0 references

0 references

10 September 2019

0 references

full work available at URL

https://arxiv.org/abs/1709.10075

0 references

zbMATH Keywords

fine-grained complexity

0 references

combinatorial pattern matching

0 references

sequence alignments

0 references

parameterized complexity

0 references

SETH

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

0 references

Consequences of Faster Alignment of Sequences

0 references

Bounds on the Complexity of the Longest Common Subsequence Problem

0 references

Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion

0 references

The longest common subsequence problem revisited

0 references

ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

0 references

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

0 references

LCS\(k\): a refined similarity measure

0 references

Q4607967

0 references

Efficient algorithms for finding a longest common increasing subsequence

0 references

On the generalized constrained longest common subsequence problems

0 references

A simple algorithm for the constrained sequence problems

0 references

Fast computation of a longest increasing subsequence and application

0 references

On Problems Equivalent to (min,+)-Convolution

0 references

A linear algorithm for 3-letter longest common weakly increasing subsequence

0 references

On computing the length of longest increasing subsequences

0 references

Algorithms for the Longest Common Subsequence Problem

0 references

A fast algorithm for computing longest common subsequences

0 references

On the complexity of \(k\)-SAT

0 references

Which problems have strongly exponential complexity?

0 references

The longest common subsequence problem for arc-annotated sequences

0 references

Q5111351

0 references

Faster algorithms for computing longest common increasing subsequences

0 references

A faster algorithm computing string edit distances

0 references

Spelling correction in systems programs

0 references

An \(O(ND)\) difference algorithm and its variations

0 references

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

0 references

Fast approximation algorithms for the diameter and radius of sparse graphs

0 references

The constrained longest common subsequence problem

0 references

The String-to-String Correction Problem

0 references

A new algorithm for optimal 2-constraint satisfaction and its implications

0 references

Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)

0 references

A fast algorithm for computing a longest common increasing subsequence

0 references

Identifiers

zbMATH Open document ID

1430.68116

0 references

DOI

10.1007/s00453-018-0485-7

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2272597