3 papers
cs.DS2026
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…
cs.DS2026
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…
cs.DS2025
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…