A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.

DOI10.4230/LIPICS.STACS.2020.41MaRDI QIDQ5874314zbMATH OpenOpenAlexFDO

Authors Lech Duraj

Publication date 7 February 2023

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

zbMATH Keywords

log-shavinglongest common increasing subsequencematching pairs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(12)

• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Longest common rollercoasters
• Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence
• A diagonal-based algorithm for the longest common increasing subsequence problem
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• A CGM Algorithm Solving the Longest Increasing Subsequence Problem
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• Combinatorial Pattern Matching
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• Longest bordered and periodic subsequences
• A space-efficient algorithm for longest common almost increasing subsequence of two sequences
• The merged longest common increasing subsequence problem

This page was built for publication: A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.

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