More on the complexity of common superstring and supersequence problems

DOI10.1016/0304-3975(92)00074-2zbMath0795.68093OpenAlexW2010332450MaRDI QIDQ1318686

Martin Middendorf

Publication date: 5 April 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(92)00074-2

zbMATH Keywords

NP-completeshortest common superstring problempermutations of stringsshortest common supersequence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items (17)

A Probabilistic PTAS for Shortest Common Superstring ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ The consensus string problem for a metric is NP-complete ⋮ Shortest common superstrings and scheduling with coordinated starting times ⋮ Improved heuristics and a genetic algorithm for finding short supersequences ⋮ A probabilistic PTAS for shortest common superstring ⋮ Hybridizations of Metaheuristics With Branch & Bound Derivates ⋮ An approximate \(A^{\ast}\) algorithm and its application to the SCS problem. ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Exact algorithms for the master ring problem ⋮ The multi-spreader crane scheduling problem: partitions and supersequences ⋮ Two-Dimensional partitioning problems ⋮ Consistent subsequences and supersequences ⋮ Minimum cost multi-product flow lines ⋮ An algorithmic analysis of the Honey-Bee game ⋮ Approximate periods of strings ⋮ Tractability and hardness of flood-filling games on trees

Cites Work

• Unnamed Item
• On finding minimal length superstrings
• The shortest common supersequence problem over binary alphabet is NP- complete
• Polynomial Complete Consecutive Information Retrieval Problems
• The Complexity of Some Problems on Subsequences and Supersequences
• Hamilton Paths in Grid Graphs

This page was built for publication: More on the complexity of common superstring and supersequence problems