An efficient algorithm for the longest common palindromic subsequence problem

DOI10.1016/J.TCS.2022.04.046MaRDI QIDQ2672607zbMATH OpenOpenAlexFDO

Authors Chang-Biau Yang, Kuo-Si Huang, Ting-Wei Liang

Publication date 13 June 2022

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

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

zbMATH Keywords

3-D dominationdiagonal methodlongest common palindromic subsequencelongest common subsequence

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On finding a longest common palindromic subsequence
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Computing a longest common palindromic subsequence
• Computing a Longest Common Palindromic Subsequence
• Anytime algorithms for the longest common palindromic subsequence problem

Cites work

• A diagonal-based algorithm for the longest common increasing subsequence problem
• A fast algorithm for computing a longest common increasing subsequence
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• A longest common subsequence algorithm suitable for similar text strings
• A subquadratic algorithm for minimum palindromic factorization
• Computing a longest common palindromic subsequence
• Computing longest common square subsequences
• Computing palindromic factorizations and palindromic covers on-line
• Counting distinct palindromes in a word in linear time
• Efficient merged longest common subsequence algorithms for similar sequences
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Faster algorithms for computing longest common increasing subsequences
• Finding approximate palindromes in strings
• scientific article; zbMATH DE number 1305083 (Why is no real title available?)
• New efficient algorithms for the LCS and constrained LCS problems
• On finding a longest common palindromic subsequence
• On Finding the Maxima of a Set of Vectors
• Palindromic length in linear time
• Palindromic subsequence automata and longest common palindromic subsequence
• The constrained longest common subsequence problem
• The generalized definitions of the two-dimensional largest common substructure problems

Cited in

(4)

• Anytime algorithms for the longest common palindromic subsequence problem
• Computing a Longest Common Palindromic Subsequence
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
• scientific article; zbMATH DE number 7696009 (Why is no real title available?)

This page was built for publication: An efficient algorithm for the longest common palindromic subsequence problem

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