Combined super-/substring and super-/subsequence problems

DOI10.1016/j.tcs.2004.02.001zbMath1068.68114OpenAlexW2030628018MaRDI QIDQ596093

Martin Middendorf, David F. Manlove

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://ul.qucosa.de/api/qucosa%3A32030/attachment/ATT-0/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Approximability of constrained LCS ⋮ On the Dedekind-MacNeille completion and formal concept analysis based on multilattices ⋮ Finitary coalgebraic multisemilattices and multilattices.

Cites Work

• Unnamed Item
• On the approximation of longest common nonsupersequences and shortest common nonsubsequences
• On finding minimal, maximal, and consistent sequences over a binary alphabet
• On finding minimal length superstrings
• The shortest common supersequence problem over binary alphabet is NP- complete
• Optimization, approximation, and complexity classes
• The shortest common nonsubsequence problem is NP-complete
• Maximal common subsequences and minimal common supersequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms on Strings, Trees and Sequences
• Linear approximation of shortest superstrings
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

This page was built for publication: Combined super-/substring and super-/subsequence problems