Maximal common subsequences and minimal common supersequences

DOI10.1006/INCO.1996.0011zbMATH Open0853.68090OpenAlexW2074728539MaRDI QIDQ1917072FDOQ1917072

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

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

zbMATH Keywords

longest minimal common supersequence problemshortest maximal common subsequence problem

Mathematics Subject Classification ID

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

Cited In (22)

• 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
• Title not available (Why is that?)
• Subsequence Packing: Complexity, Approximation, and Application
• Restricted common superstring and restricted common supersequence
• A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings
• Combined super-/substring and super-/subsequence problems
• 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
• Combinatorial Pattern Matching
• Title not available (Why is that?)
• Polynomial-delay enumeration of maximal common subsequences
• Consistent subsequences and supersequences
• Title not available (Why is that?)

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)