From the 1 of 18 linked papers with an AI index.
18 papers
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, PaweÅ Gawrychowski +2
The paper classifies the computational complexity of finding a walk with a given pattern in directed graphs whose nodes are labeled by strings, focusing on walks that traverse a bo…
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…
Optimal Enumeration of Eulerian Trails in Directed Graphs
Ben Bals, Solon P. Pissis, Matei Tinca
The BEST theorem, due to de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, is a classical tool from graph theory that links the Eulerian trails in a directed graph wit…
Subtree Mode and Applications
Jialong Zhou, Ben Bals, Matei Tinca +4
The mode of a collection of values (i.e., the most frequent value in the collection) is a key summary statistic. Finding the mode in a given range of an array of values is thus of…
Text Indexing and Pattern Matching with Ephemeral Edits
Solon P. Pissis
A sequence of edit operations in a string is called ephemeral if operation constructing string , for all with , is reverted b…