On Estimating the Average Degree of a Graph

Webpage for a paper by Oded Goldreich and Dana Ron


Following Feige, we consider the problem of estimating the average degree of a graph. Using ``neighbor queries'' as well as ``degree queries'', we show that the average degree can be approximated arbitrarily well in sublinear time, unless the graph is extremely sparse (e.g., unless the graph has a sublinear number of edges). We also provide an alternative proof of a result that is almost as good as Feige's; that is, we show that a 2-approximation of the average degree can be obtained in sublinear time in a model that only allows degree queries.

Material available on-line

Back to either Oded Goldreich's homepage. or general list of papers.