Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-013 | 10th February 2004 00:00

On Estimating the Average Degree of a Graph.



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.

ISSN 1433-8092 | Imprint