cut query model 1deterministic algorithm 1directed acyclic graphs 1reachability 1subquadratic queries 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.DS2026
Cut Query Reachability for DAGs with Subquadratic Queries
Ben Bals, Matei Tinca, Yasamin Nazari
The paper presents a deterministic algorithm for single-source reachability in directed acyclic graphs using subquadratic cut queries, achieving O(n √(n log n)) query complexity an…
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.DS2026
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…