The longest almost-increasing subsequence

DOI10.1016/J.IPL.2010.05.022MaRDI QIDQ765507zbMATH OpenOpenAlexFDO

Authors Amr Elmasry

Publication date 19 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.05.022

zbMATH Keywords

data structuresalgorithm design and analysis

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• The Longest Almost-Increasing Subsequence
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• An algorithm for the determination of longest increasing subsequence in a sequence
• Computing a longest common almost-increasing subsequence of two sequences
• Fast computation of a longest increasing subsequence and application

Cites work

• scientific article; zbMATH DE number 1962821 (Why is no real title available?)
• scientific article; zbMATH DE number 1998299 (Why is no real title available?)
• scientific article; zbMATH DE number 2226804 (Why is no real title available?)
• A fast algorithm for computing longest common subsequences
• Introduction to algorithms
• Longest Increasing and Decreasing Subsequences
• Longest increasing subsequences in sliding windows
• New clique and independent set algorithms for circle graphs
• On computing the length of longest increasing subsequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• On the longest increasing subsequence of a circular list
• Permutations, matrices, and generalized Young tableaux
• Self-adjusting binary search trees
• Tight Ω(nlgn) lower bound for finding a longest increasing subsequence

Cited in

(14)

• Computing longest (common) Lyndon subsequences
• The Longest Almost-Increasing Subsequence
• Small Longest Tandem Scattered Subsequences
• Book review of: D. Romik, The surprising mathematics of longest increasing subsequences
• Improvised divide and conquer approach for the LIS problem
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• scientific article; zbMATH DE number 5204618 (Why is no real title available?)
• On longest matching consecutive subsequence
• Computing a longest common almost-increasing subsequence of two sequences
• Longest increasing subsequences and log concavity
• The longest almost increasing subsequence problem with sliding windows
• Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
• Computing longest Lyndon subsequences and longest common Lyndon subsequences
• On the longest increasing subsequence for finite and countable alphabets

Describes a project that uses

Uses Software

• MUMMER

This page was built for publication: The longest almost-increasing subsequence

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