8 citations · 10 across the 5 of their papers we have counts for
9 papers
Longest Common Subsequence with Gap Constraints
Duncan Adamson, Maria Kosche, Tore Koß +2
We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the d…
Combinatorial Algorithms for Subsequence Matching: A Survey
Maria Kosche, Tore Koß, Florin Manea +1
In this paper we provide an overview of a series of recent results regarding algorithms for searching for subsequences in words or for the analysis of the sets of subsequences occu…
Subsequences in Bounded Ranges: Matching and Analysis Problems
Maria Kosche, Tore Koß, Florin Manea +1
In this paper, we consider a variant of the classical algorithmic problem of checking whether a given word is a subsequence of another word . More precisely, we consider the…
Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
Joel D. Day, Maria Kosche, Florin Manea +1
We consider subsequences with gap constraints, i.e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i.e., the factors of w between the pos…
Absent Subsequences in Words
Maria Kosche, Tore Koß, Florin Manea +1
An absent factor of a string is a string which does not occur as a contiguous substring (a.k.a. factor) inside . We extend this well-studied notion and define absent sub…
Robust Online Algorithms for Dynamic Choosing Problems
Sebastian Berndt, Kilian Grage, Klaus Jansen +2
Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous work…
The Edit Distance to -Subsequence Universality
Pamela Fleischmann, Maria Kosche, Tore Koß +2
A word is a subsequence of another word if can be obtained from by deleting some of its letters. The word with alph is called -subsequence universal i…
Efficiently Testing Simon's Congruence
Pawel Gawrychowski, Maria Kosche, Tore Koss +2
Simon's congruence is defined as follows: two words are -equivalent if they have the same set of subsequences of length at most . We propose an algorithm which…
Online Strip Packing with Polynomial Migration
Klaus Jansen, Kim-Manuel Klein, Maria Kosche +1
We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing heig…