1 citations · 1 across the 5 of their papers we have counts for
7 papers
Text Indexing: From Reporting to Counting
Ben Bals, Panagiotis Charalampopoulos, Oded Lachish +2
We prove an elementary yet powerful combinatorial lemma: in any rooted tree with leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is…
Faster Algorithms for Shortest Unique or Absent Substrings
Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis +2
We revisit two well-known algorithmic problems on strings: computing a shortest unique substring (SUS) and a shortest absent substring (SAS) of a string of length . Both pro…
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…
When is String Reconstruction using de Bruijn Graphs Hard?
Ben Bals, Sebastiaan van Krieken, Solon P. Pissis +2
The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly…
String Consensus Problems with Swaps and Substitutions
Estéban Gabory, Laurent Bulteau, Gabriele Fici +1
String consensus problems aim at finding a string that minimizes some given distance with respect to an input set of strings. In particular, in the Closest string problem, we are g…
Minimizing the Minimizers via Alphabet Reordering
Hilde Verbeek, Lorraine A. K. Ayad, Grigorios Loukides +1
Minimizers sampling is one of the most widely-used mechanisms for sampling strings [Roberts et al., Bioinformatics 2004]. Let be a string over a totally ordered…
Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast
Lorraine A. K. Ayad, Grigorios Loukides, Solon P. Pissis +1
Sparse suffix sorting is the problem of sorting suffixes of a string of length . Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite…