Algorithm Design and Engineering Group 

Department of Computer and System Sciences, University of Rome "La Sapienza"  

Paper information 
In proceedings 
Camil Demetrescu, Irene Finocchi, Andrea Ribichini Trading off space for passes in graph streaming problems in Proceedings of the 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'06), pp. 714723, 2006. 
Abstract 
A natural question in data stream processing is whether we can reduce the space usage at the price of increasing the number of passes over the data. Unfortunately, this seems to be very hard for many graph problems, unless powerful primitives such as sorting are used. And yet, even using sorting, problems such as shortest paths remain difficult. In this talk we show that, for any space restriction of s bits, singlesource shortest paths in directed graphs with small positive integer edge weights can be solved in O((n log^3/2 n)/sqrt(s)) passes. For undirected connectivity, we devise an O((n log n)/s) passes algorithm. Both problems require Omega(n/s) passes under the restrictions we consider. Our algorithms do not use sorting as a primitive and work in the WStream model introduced by Aggarwal et al. in FOCS 2004. 