65 citations · 333 across the 44 of their papers we have counts for
51 papers
Sensitivity of Repetitiveness Measures to String Reversal
Hideo Bannai, Yuto Fujie, Peaker Guo +4
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, , of runs in the run-leng…
Compressed Dictionary Matching on Run-Length Encoded Strings
Philip Bille, Inge Li Gørtz, Simon J. Puglisi +1
Given a set of pattern strings and a text string , the classic dictionary matching problem is to report all occurrences of each pattern in…
Height-bounded Lempel-Ziv encodings
Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian +2
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access…
Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
Matthias Bentert, Klaus Heeger, Tomohiro Koana
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal i…
Longest Common Prefix Arrays for Succinct k-Spectra
Jarno N. Alanko, Elena Biagi, Simon J. Puglisi
The k-spectrum of a string is the set of all distinct substrings of length k occurring in the string. K-spectra have many applications in bioinformatics including pseudoalignment a…
Maximal Closed Substrings
Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici +1
A string is closed if it has length 1 or has a nonempty border without internal occurrences. In this paper we introduce the definition of a \emph{maximal closed substring} (MCS), w…