1 citations · 3 across the 5 of their papers we have counts for
8 papers
Coloring powers of random graphs
Alan Frieze, Ross Kang, Aditya Raut +2
Given a graph and an integer , the th power of is the graph obtained from by adding edges for all pairs of distinct vertices at distance at most fr…
Elastic-Degenerate String Comparison
Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti +4
An elastic-degenerate (ED) string is a sequence of sets containing strings in total whose cumulative length is . We call , , and the len…
Elastic-Degenerate String Matching with 1 Error
Giulia Bernardini, Estéban Gabory, Solon P. Pissis +3
An elastic-degenerate string is a sequence of finite sets of strings of total length , introduced to represent a set of related DNA sequences, also known as a pangenome. The…
Convergence of the number of period sets in strings
Eric Rivals, Michelle Sweering, Pengfei Wang
Consider words of length . The set of all periods of a word of length is a subset of . However, any subset of is not necessarily…
A Universal Error Measure for Input Predictions Applied to Online Graph Problems
Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela +3
We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a ge…
String Sampling with Bidirectional String Anchors
Grigorios Loukides, Solon P. Pissis, Michelle Sweering
The minimizers sampling mechanism is a popular mechanism for string sampling introduced independently by Schleimer et al. [SIGMOD 2003] and by Roberts et al. [Bioinf. 2004]. Given…
String Sanitization Under Edit Distance: Improved and Generalized
Takuya Mieno, Solon P. Pissis, Leen Stougie +1
Let be a string of length over an alphabet , be a positive integer, and be a set of length- substrings of . The ETFS problem asks us to construct…
Combinatorial Algorithms for String Sanitization
Giulia Bernardini, Huiping Chen, Alessio Conte +6
String data are often disseminated to support applications such as location-based service provision or DNA sequence analysis. This dissemination, however, may expose sensitive patt…