### DIMACS Theoretical Computer Science Seminar

Title: Estimating the weight of Euclidean minimum spanning trees in a data
stream

Speaker: **Christian Sohler**, University of Paderborn, Germany

Date: March 8, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We consider the problem to compute the Euclidean minimum spanning
tree of a set of n points in the R^d in the data streaming model.
In this model the input point set is given sequentially,
i.e. we can access the points one after the other. No random access
to the input set is possible. Additionally, a streaming algorithm
should use at most polylogarithmic space in the number of input
points.

Since the representation of a minimum spanning tree has size
Omega(n), we focus on estimating the weight of the spanning tree.
We develop a streaming algorithm that computes with probability
1-delta a 1+epsilon approximation of the weight of the Euclidean
minimum spanning tree. Our algorithm uses poly(log n, 1/epsilon, log
1/delta)
space and requires that a rough (polynomial) approximation of the
number of points in the stream is known.

Joint work with Gereon Frahling.

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html