ICE-TCS Seminar: Christian Konrad
Time: Friday, January 17, 2pm
Location: M1.08, Reykjavík University, Menntavegur 1
Title: On the Order of Graph Streams
Speaker: Christian Konrad
While classical graph algorithms assume random access to the input graph, a graph streaming algorithm receives a sequence of the edges of an input graph and processes them one-by-one in sequential order while using sublinear memory. Graph streaming algorithms are motivated by the fact that modern graphs (e.g. the facebook graph) exceed the size of a computer's RAM by far, and often it is too costly or even impossible to grant an algorithm a more complex data access scheme than sequential access.
In this talk, we explore the importance of the order in which the streaming algorithm receives the graph edges. Are there problems that become easier if we assume that edges arrive in uniform random order instead of worst-case order? Are there other particular orders that make sense to consider? We address these questions via concrete examples with a focus on the bipartite matching problem and the semi-matching problem. We conclude that restrictions on the order of graph streams have a strong impact on the space complexity of streaming algorithms.