Restricted Common Superstring and Restricted Common Supersequence

DOI10.1007/978-3-642-21458-5_39zbMath1342.68143OpenAlexW1547982388MaRDI QIDQ3011876

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

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

Related Items (5)

The constrained shortest common supersequence problem ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ The multi-spreader crane scheduling problem: partitions and supersequences ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ Quick greedy computation for minimum common string partition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The shortest common supersequence problem over binary alphabet is NP- complete
• Optimization, approximation, and complexity classes
• The shortest common nonsubsequence problem is NP-complete
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Multiple Alignment, Communication Cost, and Graph Matching
• The Complexity of Some Problems on Subsequences and Supersequences
• String Noninclusion Optimization Problems
• Linear approximation of shortest superstrings
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Restricted Common Superstring and Restricted Common Supersequence