scientific article; zbMATH DE number 6850388

zbMath1403.68369arXiv1803.00938MaRDI QIDQ4607967

Marvin Künnemann, Karl Bringmann

Publication date: 15 March 2018

Full work available at URL: https://arxiv.org/abs/1803.00938

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (19)

Scattered Factor-Universality of Words ⋮ Computing the longest common almost-increasing subsequence ⋮ The complexity of binary matrix completion under diameter constraints ⋮ 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 ⋮ Absent subsequences in words ⋮ Unnamed Item ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry

This page was built for publication: