2 papers
cs.DS2025
Constant Approximation of Arboricity in Near-Optimal Sublinear Time
Jiangqi Dai, Mohsen Ghaffari, Julian Portmann
We present a randomized algorithm that computes a constant approximation of a graph's arboricity, using queries to adjacency lists and in the same time bound. Here…
cs.DC2024
Shared Randomness Helps with Local Distributed Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +5
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is loca…