New Heuristic and Multivalued Decision Diagram-based Exact Algorithms for Repetition-Free Longest Common Subsequence Problems
Abstract
The longest common subsequence (LCS) problem is one of the fundamental problems in string algorithms. A constrained version, the repetitionfree longest common subsequence (RFLCS) problem, additionally requires that each character may appear at most once in the solution sequence. In sharp contrast to LCS, RFLCS is NP-hard and even APX-hard. Previous work has shown that multivalued decision diagrams (MDDs) provide an effective tool for solving the RFLCS problem to optimality.
Fields of Study & Subjects
Algorithms and Data Compression
Genome Rearrangement Algorithms
Network Packet Processing and Optimization
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 233–245
- Publication date
- 1 January 2026
- Language
- EN