More on the complexity of common superstring and supersequence problems

DOI10.1016/0304-3975(92)00074-2MaRDI QIDQ1318686zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Restricted common superstring and restricted common supersequence
• Combined super-/substring and super-/subsequence problems
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Maximal common subsequences and minimal common supersequences
• Approximation algorithms for the shortest common superstring problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hamilton Paths in Grid Graphs
• On finding minimal length superstrings
• Polynomial Complete Consecutive Information Retrieval Problems
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common supersequence problem over binary alphabet is NP- complete

Cited in

(21)

• A probabilistic PTAS for shortest common superstring
• Improved heuristics and a genetic algorithm for finding short supersequences
• The multi-spreader crane scheduling problem: partitions and supersequences
• A Survey on the Complexity of Flood-Filling Games
• Shortest common superstrings and scheduling with coordinated starting times
• Restricted common superstring and restricted common supersequence
• Combined super-/substring and super-/subsequence problems
• The consensus string problem for a metric is NP-complete
• scientific article; zbMATH DE number 2239908 (Why is no real title available?)
• Hybridizations of metaheuristics with branch \& bound derivates
• An algorithmic analysis of the Honey-Bee game
• Longest common subsequence problem for unoriented and cyclic strings
• Minimum cost multi-product flow lines
• An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.
• A Probabilistic PTAS for Shortest Common Superstring
• Exact algorithms for the master ring problem
• Two-Dimensional partitioning problems
• Consistent subsequences and supersequences
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Tractability and hardness of flood-filling games on trees
• Approximate periods of strings

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

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