Improved Algorithms for Edge Colouring in the W-Streaming Model

2020/10/27 by Charikar, Moses, Liu, Paul
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2010.14560

Abstract

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²) 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² n) space when the edges arrive according to a uniformly random permutation. The second algorithm uses (1 + o(1))Δ² / s colours in O(n s) space when edges arrival adversarially.

Related

• Improved Streaming Edge Coloring
• Streaming Edge Coloring with Subquadratic Palette Size
• Low-Memory Algorithms for Online and W-Streaming Edge Coloring
• Streaming Edge Coloring with Asymptotically Optimal Colors
• Coloring in Graph Streams