An Algorithm for a Variation of the Shortest Common Superstring Problem

2024/10/30 by A. R. Gilfanov, Gilfanov, Arthur
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2410.23900

openalex publication_date 2024/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This study develops an algorithm to solve a variation of the Shortest Common Superstring (SCS) problem. There are two modifications to the base SCS problem. First, one string in the set S is allowed to have up to K mistakes, defined as not matching the SCS in at most K positions. Second, no string in S can be a substring of another in S. The algorithm proposed for the problem is exact.

Related

• On improving the approximation ratio of the r-shortest common superstring problem
• All instantiations of the greedy algorithm for the shortest superstring problem are equivalent
• Approximation hardness of Shortest Common Superstring variants
• Greedy Shortest Common Superstring Approximation in Compact Space
• Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios