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

DOI10.1007/978-3-031-43980-3_30MaRDI QIDQ6545446FDOQ6545446

Authors: Lusheng Wang, Binhai Zhu 

Publication date: 29 May 2024

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

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)

Cites Work

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

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)