A hardness result and new algorithm for the longest common palindromic subsequence problem

DOI10.1016/j.ipl.2017.08.006zbMath1420.68246arXiv1612.07475OpenAlexW2564828573MaRDI QIDQ2410574

Heikki Hyyrö, Shunsuke Inenaga

Publication date: 18 October 2017

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

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

zbMATH Keywords

longest common subsequencesstring processingpalindromic subsequencesnesting rectangles

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (10)

Longest common rollercoasters ⋮ Computing longest (common) Lyndon subsequences ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ An efficient algorithm for the longest common palindromic subsequence problem ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Longest bordered and periodic subsequences ⋮ Faster STR-EC-LCS Computation ⋮ Longest property-preserved common factor: a new string-processing framework ⋮ Unnamed Item ⋮ Anytime algorithms for the longest common palindromic subsequence problem

Cites Work

• Unnamed Item
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Quadratic-time algorithm for a string constrained LCS problem
• Doubly-constrained LCS and hybrid-constrained LCS problems revisited
• Constrained sequence analysis algorithms in computational biology
• Computing a longest common subsequence for a set of strings
• Regular expression constrained sequence alignment
• New efficient algorithms for the LCS and constrained LCS problems
• A faster algorithm computing string edit distances
• The string merging problem
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• A simple algorithm for the constrained sequence problems
• Regular Language Constrained Sequence Alignment Revisited
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• Computing a Longest Common Palindromic Subsequence

This page was built for publication: A hardness result and new algorithm for the longest common palindromic subsequence problem