Computing a longest common almost-increasing subsequence of two sequences

DOI10.1016/J.TCS.2020.11.035MaRDI QIDQ2220858zbMATH OpenOpenAlexFDO

Authors Toan Thang Ta, Yi-Kung Shieh, Chin Lung Lu

Publication date 25 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.11.035

zbMATH Keywords

dynamic programminglongest common almost-increasing subsequence

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• A fast algorithm for computing a longest common increasing subsequence
• A linear space algorithm for computing a longest common increasing subsequence
• Faster algorithms for computing longest common increasing subsequences
• Faster Algorithms for Computing Longest Common Increasing Subsequences

Cites work

• A fast algorithm for computing a longest common increasing subsequence
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• Longest Increasing and Decreasing Subsequences
• Permutations, matrices, and generalized Young tableaux
• The longest almost-increasing subsequence
• The String-to-String Correction Problem
• Tight Ω(nlgn) lower bound for finding a longest increasing subsequence

Cited in

(7)

• Computing the longest common almost-increasing subsequence
• Computing longest (common) Lyndon subsequences
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• Computing longest Lyndon subsequences and longest common Lyndon subsequences
• The longest almost increasing subsequence problem with sliding windows
• A space-efficient algorithm for longest common almost increasing subsequence of two sequences
• The longest almost-increasing subsequence

Describes a project that uses

Uses Software

• MUMMER

This page was built for publication: Computing a longest common almost-increasing subsequence of two sequences

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