Algorithms and hardness for the longest common subsequence of three strings and related problems

DOI10.1007/978-3-031-43980-3_30MaRDI QIDQ6545446zbMATH OpenFDO

Authors Lusheng Wang, Binhai Zhu

Publication date 29 May 2024

zbMATH Keywords

NP-completenesslongest common subsequencepolynomial-time algorithmslongest cubic subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Recommendations

• Computing longest common square subsequences
• Longest Square Subsequence Problem Revisited
• Algorithms for the longest common subsequence problem for multiple strings based on geometric maxima
• Constrained LCS: Hardness and Approximation
• The constrained longest common subsequence problem

Cites work

• A longest common subsequence algorithm suitable for similar text strings
• A new efficient algorithm for computing the longest common subsequence
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Computing the longest common almost-increasing subsequence
• Longest Square Subsequence Problem Revisited
• Multivariate fine-grained complexity of longest common subsequence
• On Cartesian Trees and Range Minimum Queries
• On space efficient two dimensional range minimum data structures
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Semi-local string comparison: algorithmic techniques and applications
• String Processing and Information Retrieval
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(1)

• The longest subsequence-repeated subsequence problem

This page was built for publication: Algorithms and hardness for the longest common subsequence of three strings and related problems

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