colouring

• Improved Algorithms for Edge Colouring in the W-Streaming Model

  SOSA@SODA 2021

  Paul Liu and Moses Charikar

  ---

  In the W-streaming model, an algorithm is given $O(n \text{polylog} n)$ space and must process a large graph of up to $O(n^2)$ edges. In this short note we give two algorithms for edge colouring under the W-streaming model. For edge colouring in W-streaming, a colour for every edge must be determined by the time all the edges are streamed. Our first algorithm uses $\Delta+o(\Delta)$ colours in $O(n \log^2 n)$ space when the edges arrive according to a uniformly random permutation. The second algorithm uses $(1+o(1))\Delta^2/s$ colours in $\tilde{O}(ns)$ space when edges arrival adversarially.

  graph algorithms streaming colouring

  [pdf] [slides] [video]