Graph Problems in the Streaming Model

演讲人: Sampath Kannan University of Pennsylvania
时间: 2006-10-19 14:00-2006-10-19 15:00
地点:FIT Building,Tsinghua University

We describe a recent model of computation called the streaming model. This model captures the increasingly common situation where the volume of data processed by a computer is much larger than what will fit in memory. An added restriction is that the computer is required to process each data item in "real time". We provide positive and negative results on the existence of algorithms for some classical graph problems such as matching and computing distances in this model.(Joint work with J. Feigenbaum, A. McGregor, S. Suri, and J. Zhang)