**Friday, 15:15 - 15:40 h, Room: H 3012**

**Christian Konrad**

On the order of graph streams

**Abstract:**

While classical graph algorithms assume random access to the input graph, a semi-streaming algorithm receives a sequence of edges of the input graph and processes them one-by-one in sequential order while using small memory. How important is the order in which the edges arrive? 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 two concrete examples: the unweighted bipartite graph matching problem and the unweighted semi-matching problem: given a bipartite graph (*A, B, E*), in the semi-matching problem we aim to match all *A* vertices to *B* vertices such that the maximal degree of the *B* vertices is minimized.

The talk concludes with a review on open problems in this area of research.

Talk 1 of the invited session Fri.3.H 3012

**"Graph optimization problems in the streaming model"** [...]

Cluster 2

**"Combinatorial optimization"** [...]