Improved Algorithms for Edge Colouring in the W-Streaming Model
Moses Charikar, Paul Liu · Society for Industrial and Applied Mathematics eBooks · 2021
In the W-streaming model, an algorithm is given O(n polylog n) space and must process a large graph of up to O(n2) 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 log2 n) space when the edges arrive according to a uniformly random permutation. The second algorithm uses (1 + o(1))Δ2/s colours in Õ(ns) space when edges arrival adversarially.