TR04-013 Authors: Oded Goldreich, Dana Ron

Publication: 11th February 2004 10:57

Downloads: 2301

Keywords:

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.