Restricted common superstring and restricted common supersequence

DOI10.1007/978-3-642-21458-5_39MaRDI QIDQ3011876zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Zvi Gotthilf, Alexandru Popa, Moshe Lewenstein

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21458-5_39

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• More on the complexity of common superstring and supersequence problems
• The constrained shortest common supersequence problem
• Restricted and swap common superstring: a multivariate algorithmic perspective
• Maximal common subsequences and minimal common supersequences
• Approximation algorithms for the shortest common superstring problem

Cites work

• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 432770 (Why is no real title available?)
• scientific article; zbMATH DE number 3599517 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 1754594 (Why is no real title available?)
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• Linear approximation of shortest superstrings
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Multiple Alignment, Communication Cost, and Graph Matching
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Optimization, approximation, and complexity classes
• String Noninclusion Optimization Problems
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common nonsubsequence problem is NP-complete
• The shortest common supersequence problem over binary alphabet is NP- complete

Cited in

(8)

• Shortest common superstrings and scheduling with coordinated starting times
• More on the complexity of common superstring and supersequence problems
• Quick greedy computation for minimum common string partition
• The multi-spreader crane scheduling problem: partitions and supersequences
• The constrained shortest common supersequence problem
• Restricted and swap common superstring: a parameterized view
• Restricted and swap common superstring: a multivariate algorithmic perspective
• On the greedy algorithm for the shortest common superstring problem with reversals

This page was built for publication: Restricted common superstring and restricted common supersequence

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