Title: A Size-Estimation Technique

Abstract:

I will present a simple and cute technique by Edith Cohen for
estimating the sizes of some desired sets.  Her technique is
illustrated via two examples: (1) Given a directed graph, let the
reachability set of a node v be the set of nodes reachable from v,
and we would like to estimate the sizes of the reachability sets
of all the nodes in the graph.  (2) Given a directed graph, let
the d-neighborhood of a node v be the set of nodes whose distance
from v is at most d, and we want to estimate the sizes of the
d-neighborhood for all v and all d.  The algorithm runs in time
O(m polylog(n)), where n is the number of nodes and m is the
number of edges in the graph.  The estimates obtained are
(1+epsilon)-approximations of the accurate sizes with high
probability.