Title: Streaming Algorithms for Graph Problems
Speaker: Sampath Kannan
Date: May 3, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
We consider algorithms for various common graph problems in the streaming model. For graphs with n vertices and m edges, we conclude that o(n) space is insufficient for any interesting problem. We then focus on what can be computed in space n polylog n with one or more passes. We show approximation an approximation algorithm for problems such as matching, diameter, distances between queried pairs of vertices, etc. and prove matching lower bounds in some cases.
Joint work with Andrew McGregor, Sid Suri, Jian Zhang, and Joan Feigenbaum
See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html