Enumeration of maximal common subsequences between two strings

DOI10.1007/s00453-021-00898-5OpenAlexW4206410708MaRDI QIDQ2118209

Takeaki Uno, Giulia Punzi, Alessio Conte, Roberto Grossi

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00898-5

zbMATH Keywords

enumerationsubsequenceLCSmaximal common subsequencepolynomial-delay

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes

Uses Software

• MUMMER

Cites Work

• Unnamed Item
• Computing a longest common subsequence for a set of strings
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• A faster algorithm computing string edit distances
• Directed acyclic subsequence graph -- overview
• Maximal common subsequences and minimal common supersequences
• Maximal common subsequence algorithms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Maximal Common Subsequence Algorithms
• On the Enumeration of Minimal Dominating Sets and Related Notions
• On the complexity of \(k\)-SAT

This page was built for publication: Enumeration of maximal common subsequences between two strings