Showing cs.DSShow all
2 papers · 1 filter
cs.DS2021
Approximating the Arboricity in Sublinear Time
Talya Eden, Saleet Mossel, Dana Ron
We consider the problem of approximating the arboricity of a graph , which we denote by , in sublinear time, where the arboricity of a graph is the minim…
cs.DS2020
Sampling Multiple Edges Efficiently
Talya Eden, Saleet Mossel, Ronitt Rubinfeld
We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise -close to the uniform distribution, in an \emph{amortized-ef…