Polynomial-delay enumeration of maximal common subsequences

DOI10.1007/978-3-030-32686-9_14MaRDI QIDQ6536255zbMATH OpenFDO

Authors Alessio Conte, Roberto Grossi, Giulia Punzi, Takeaki Uno

Publication date 19 April 2024

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Recommendations

• Enumeration of maximal common subsequences between two strings
• Maximal common subsequence algorithms
• Maximal common subsequence algorithms
• Maximal common subsequences and minimal common supersequences

Cites work

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• Algorithms for the Longest Common Subsequence Problem
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• Maximal common subsequence algorithms
• Maximal common subsequences and minimal common supersequences
• On the enumeration of minimal dominating sets and related notions
• Sparse dynamic programming I
• The String-to-String Correction Problem

Cited in

(1)

• Chaining of maximal exact matches in graphs

This page was built for publication: Polynomial-delay enumeration of maximal common subsequences

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