More on the complexity of common superstring and supersequence problems

DOI10.1016/0304-3975(92)00074-2zbMATH Open0795.68093OpenAlexW2010332450MaRDI QIDQ1318686FDOQ1318686

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

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

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)

Cites Work

• Title not available (Why is that?)
• Hamilton Paths in Grid Graphs
• On finding minimal length superstrings
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common supersequence problem over binary alphabet is NP- complete
• Polynomial Complete Consecutive Information Retrieval Problems

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
• Title not available (Why is that?)
• 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
• Approximate periods of strings
• Tractability and hardness of flood-filling games on trees

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)