Restricted Common Superstring and Restricted Common Supersequence

DOI10.1007/978-3-642-21458-5_39zbMath1342.68143MaRDI 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

68R05: Combinatorics in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

68W32: Algorithms on strings

Related Items

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

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