A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

DOI10.4230/lipics.isaac.2020.4arXiv2003.13589OpenAlexW3118057770MaRDI QIDQ6065393

Paweł Gawrychowski, Unnamed Author

Publication date: 14 November 2023

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

zbMATH Keywords

longest common increasing subsequencefour russians

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (3)

Longest common rollercoasters ⋮ Longest bordered and periodic subsequences ⋮ Simon's congruence pattern matching

Cites Work

• Unnamed Item
• Unnamed Item
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Faster algorithms for computing longest common increasing subsequences
• A fast algorithm for computing a longest common increasing subsequence
• A linear space algorithm for computing a longest common increasing subsequence
• A new data structure for representing sorted lists
• An almost optimal algorithm for unbounded searching
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Tight conditional lower bounds for longest common increasing subsequence
• Fast and compact regular expression matching
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Faster Regular Expression Matching
• A Fast Merging Algorithm
• A Four Russians algorithm for regular expression pattern matching
• The String-to-String Correction Problem
• Faster All-Pairs Shortest Paths via Circuit Complexity
• A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.

This page was built for publication: A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem