Improved Algorithms for Edge Colouring in the W-Streaming Model

10/27/2020

∙

by   Moses Charikar, et al.

∙

0

∙

share

In the W-streaming model, an algorithm is given O(n 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 Δ + o(Δ) 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))Δ^2 / s colours in Õ(n s) space when edges arrival adversarially.