ECCC-Report TR04-013https://eccc.weizmann.ac.il/report/2004/013Comments and Revisions published for TR04-013en-usWed, 11 Feb 2004 10:57:34 +0200
Paper TR04-013
| On Estimating the Average Degree of a Graph. |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2004/013Following 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.
Wed, 11 Feb 2004 10:57:34 +0200https://eccc.weizmann.ac.il/report/2004/013