Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries

Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri

We revisit the problem of designing sublinear algorithms for estimating the average degree of an $n$-vertex graph. The standard access model for graphs allows for the following que…