Restricted Common Superstring and Restricted Common Supersequence
From MaRDI portal
Publication:3011876
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
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