Maximal common subsequences and minimal common supersequences

DOI10.1006/INCO.1996.0011MaRDI QIDQ1917072zbMATH OpenOpenAlexFDO

Authors Campbell B. Fraser, Robert W. Irving

Publication date 2 January 1997

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

Full work available at URL https://semanticscholar.org/paper/3faabc83780a93018cf25b0be628424784df58c5

zbMATH Keywords

longest minimal common supersequence problemshortest maximal common subsequence problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the approximation of shortest common supersequences and longest common subsequences
• On finding minimal, maximal, and consistent sequences over a binary alphabet
• scientific article; zbMATH DE number 1555947
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

Cited in

(22)

• scientific article; zbMATH DE number 4095235 (Why is no real title available?)
• Local search for string problems: brute-force is essentially optimal
• Enumeration of maximal common subsequences between two strings
• On the longest common rigid subsequence problem
• More on the complexity of common superstring and supersequence problems
• Longest common subsequences
• Finding the longest common nonsuperstring in linear time
• scientific article; zbMATH DE number 3900178 (Why is no real title available?)
• Restricted common superstring and restricted common supersequence
• Subsequence Packing: Complexity, Approximation, and Application
• Combined super-/substring and super-/subsequence problems
• A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings
• Maximal common subsequence algorithms
• Maximal common subsequence algorithms
• Non-overlapping common substrings allowing mutations
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• The generalized definitions of the two-dimensional largest common substructure problems
• Analogical proportions in a lattice of sets of alignments built on the common subwords in a finite language
• scientific article; zbMATH DE number 1555947 (Why is no real title available?)
• Combinatorial Pattern Matching
• Consistent subsequences and supersequences
• Polynomial-delay enumeration of maximal common subsequences

This page was built for publication: Maximal common subsequences and minimal common supersequences

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