Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUBLINEAR-TIME:
Reports tagged with Sublinear-time:
TR05-073 | 14th July 2005
Oded Goldreich, Dana Ron

#### Approximating Average Parameters of Graphs.

Inspired by Feige ({\em 36th STOC}, 2004),
we initiate a study of sublinear randomized algorithms
for approximating average parameters of a graph.
Specifically, we consider the average degree of a graph
and the average distance between pairs of vertices in a graph.
Since our focus is on sublinear algorithms, ... more >>>

ISSN 1433-8092 | Imprint