Computing and Enumerating Minimal Common Supersequences Between Two Strings

Braeden Sopp, Adiesha Liyanage, Mingyang Gong, Binhai Zhu · 2026

Read Computing and Enumerating Minimal Common Supersequences Between Two Strings by Braeden Sopp, Adiesha Liyanage, Mingyang Gong, Binhai Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22591.txt.

Description

Sopp and co-authors study minimal common supersequences for two strings. A supersequence contains both strings inside it, in order, but not always side by side. The shortest such string is a classic textbook problem. The minimal form studied here is a weaker, cheaper target. The authors show one minimal supersequence can be found in linear time. They also give a way to list all of them. Their listing method uses quadratic space and linear delay between results. Building its data structure takes cubic time.

Catalog record

CREATORBraeden Sopp, Adiesha Liyanage, Mingyang Gong, Binhai Zhu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54236
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22591

Browse the full library · About the Tower of Babel