On Estimating the Average Degree of a Graph
Webpage for a paper by Oded Goldreich and Dana Ron
Abstract
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.