7 citations · 10 across the 8 of their papers we have counts for
34 papers
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
Faster Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
We consider the approximate pattern matching problem under the edit distance. Given a text of length , a pattern of length , and a threshold , the task is to find…
Computing Longest (Common) Lyndon Subsequences
Hideo Bannai, Tomohiro I, Tomasz Kociumaka +2
Given a string with length whose characters are drawn from an ordered alphabet of size , its longest Lyndon subsequence is a longest subsequence of that is a Lyndon…
Small space and streaming pattern matching with k edits
Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya
In this work, we revisit the fundamental and well-studied problem of approximate pattern matching under edit distance. Given an integer , a pattern of length , and a text…
Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka, Saeed Seddighin
We study dynamic algorithms for the longest increasing subsequence (\textsf{LIS}) problem. A dynamic \textsf{LIS} algorithm maintains a sequence subject to operations of the follow…
Tight Bound for the Number of Distinct Palindromes in a Tree
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter +1
For an undirected tree with edges labelled by single letters, we consider its substrings, which are labels of the simple paths between pairs of nodes. We prove that there are $…