Algorithms for the Shortest Common Superstring Problem

Title

Algorithms for the Shortest Common Superstring Problem

Subject

Theoretical Computer Science

Creator

Aastha Popat

Date

2025

Contributor

Artur Czumaj

Abstract

The Shortest (Common) Superstring problem (SSP) is a classical optimisation problem on strings (texts): to find a shortest text that contains all input texts. This problem is known to be NP-hard and therefore the main research has been concentrating on the design of fast and good approximation algorithms for it. Many constant-factor approximation algorithms have been designed, including in particular the GREEDY algorithm. The aim of this research is to understand what this algorithm does and analyse how close it gets to the optimal solution, using graph-theoretic algorithms and empirical data.

Meta Tags

Theory, foundations, computer science, mathematics, algorithms, algorithm, theoretical computer science, NP, NP hard, NP-hard, strings, text, texts

Files

Citation

Aastha Popat, “Algorithms for the Shortest Common Superstring Problem,” URSS SHOWCASE, accessed November 2, 2025, https://urss.warwick.ac.uk/items/show/1034.