4 papers · 1 filter
Computing and Enumerating Minimal Common Supersequences Between Two Strings
Braeden Sopp, Adiesha Liyanage, Mingyang Gong +1
Given \(k\) strings each of length at most , computing the shortest common supersequence of them is a well-known NP-hard problem (when \(k\) is unbounded). On the other hand, wh…
Computing Maximal Repeating Subsequences in a String
Mingyang Gong, Adiesha Liyanage, Braeden Sopp +1
In this paper we initiate the study of computing a maximal (not necessarily maximum) repeating pattern in a single input string, where the corresponding problems have been studied…
Fast Order Statistics with Group Inequality Testing
Adiesha Liyanage, Brendan Mumey, Braeden Sopp
Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, determining the rank of…
The Longest Subsequence-Repeated Subsequence Problem
Manuel Lafond, Wenfeng Lai, Adiesha Liyanage +1
Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-repeated subsequence (LSRS) is proposed. Given a sequence of…