The longest subsequence-duplicated subsequence and related problems

DOI10.1016/J.IC.2025.105313MaRDI QIDQ6931993zbMATH OpenFDO

Authors Manuel Lafond, Wenfeng Lai, Adiesha Liyanage, Binhai Zhu

Publication date 9 September 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105313

zbMATH Keywords

dynamic programminglongest common subsequencelongest letter-duplicated subsequenceNP-completenesstandem duplications

Mathematics Subject Classification ID

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

Cites work

• 2726. A problem on strings of beads
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Approximation algorithms for the longest run subsequence problem
• Beyond the longest letter-duplicated subsequence problem
• Computing the tandem duplication distance is NP-hard
• Longest Square Subsequence Problem Revisited
• Quadratic conditional lower bounds for string problems and dynamic time warping
• String Processing and Information Retrieval
• The longest letter-duplicated subsequence and related problems
• The longest subsequence-repeated subsequence problem
• The Tandem Duplication Distance Is NP-Hard
• The tandem duplication distance problem is hard over bounded alphabets

This page was built for publication: The longest subsequence-duplicated subsequence and related problems

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