1 citations · 1 across the 7 of their papers we have counts for
9 papers
Mining Correlated Motifs with Wildcards in PPI Networks: Exact and Optimal
Lucas P. Oliveira, Ben Bals, Aalt D. J. van Dijk +1
A protein-protein interaction (PPI) network is a graph whose nodes are protein sequences and whose edges represent physical interactions between proteins. Correlated Motif Mining (…
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…
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graph…
Cut Query Reachability for DAGs with Subquadratic Queries
Ben Bals, Matei Tinca, Yasamin Nazari
In the cut-query model, we have access to a (directed) graph via an oracle and we can query the size of the (directed) cut of a given subset of the vertices. One of the most elemen…
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…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
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…
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…
Testing Quasiperiodicity
Christine Awofeso, Ben Bals, Oded Lachish +1
A cover (or quasiperiod) of a string is a shorter string such that every position of is contained in some occurrence of as a substring. The notion of covers was int…