On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

Marko Djukanović, Nikola Balaban, Christian Blum, Aleksandar Kartelj, Sašo Džeroski, Žiga Zebec · 2026

Read On Solving the Multiple Variable Gapped Longest Common Subsequence Problem by Marko Djukanović, Nikola Balaban, Christian Blum, Aleksandar Kartelj, Sašo Džeroski, Žiga Zebec (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-2604-18645.txt.

Description

Djukanović and five colleagues tackle Variable Gapped Longest Common Subsequence, which loosens classic LCS with flex gaps. The task shows up in gene-string matching with spacing rules, and in time-series work with set delays. They search via root-based state graphs, where the space holds many rooted subgraphs. To tame the blowup, repeated beam search keeps a shared pool of strong root nodes. In a first full test on 320 made-up cases of up to 10 strings and 500 letters, the method beats plain beam search at like runtimes.

Catalog record

CREATORMarko Djukanović, Nikola Balaban, Christian Blum, Aleksandar Kartelj, Sašo Džeroski, Žiga Zebec
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39307
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel