论文标题
改进的W流式模型中边缘着色的算法
Improved Algorithms for Edge Colouring in the W-Streaming Model
论文作者
论文摘要
在W流式模型中，给出了一个算法$ O（n \ mathrm {polylog} n）$ space，并且必须处理最多$ o（n^2）$边缘的大图。在此简短的说明中，我们给出了W流式模型下边缘着色的两种算法。对于W-streaming中的边缘着色，每个边缘的颜色都必须由所有边缘流的时间确定。当边缘根据均匀的随机置换时到达时，我们的第一个算法使用$δ+ o（δ）$颜色在$ o（n \ log^2 n）$空间中。第二算法使用$（1 + o（1））δ^2 / s $颜色在$ \ tilde {o}（n s）$ space中的$（n s）$ space时，边缘在对流时到达。
In the W-streaming model, an algorithm is given $O(n \mathrm{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 $\tilde{O}(n s)$ space when edges arrival adversarially.
