论文标题
即使是最简单的图形着色问题也不容易流媒体！
Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!
论文作者
论文摘要
我们研究了一个否则容易的图形着色问题，但在一通流模型中变得非常普遍。与试图找到对顶点的颜色分配的流媒体上的图形着色问题相反，我们的主要工作是估计具有与图形一起流的着色函数的相互冲突或单色边缘的数量；我们称问题{\ sc冲突 - }。仅当在流中揭示顶点时，才能读取或访问顶点上的着色函数。如果我们需要在过去流过的顶点上的颜色，那么该颜色及其顶点必须明确存储。我们为图形提供算法，该算法是在一通顶点到达流型模型的不同变体中流中流的算法。 {\ sc顶点到达}（{\ sc va}），{certex到达，带有oracle}（{\ sc vadeg}），{\ sc sc vertex以随机顺序}（{\ sc varand}）模型，并以随机订单模型为特定。我们还提供大多数情况下的匹配下限。我们工作的主要工作是表明，随机顺序流的属性可以利用到设计流算法来估计边缘数量的数量。对于随机订单模型，我们还获得了下限，尽管与上限不匹配。在有关此问题的所有三个模型中，我们可以显示出明确的权力分离，而有利于{\ sc varand}模型。
We study a graph coloring problem that is otherwise easy but becomes quite non-trivial in the one-pass streaming model. In contrast to previous graph coloring problems in streaming that try to find an assignment of colors to vertices, our main work is on estimating the number of conflicting or monochromatic edges given a coloring function that is streaming along with the graph; we call the problem {\sc Conflict-Est}. The coloring function on a vertex can be read or accessed only when the vertex is revealed in the stream. If we need the color on a vertex that has streamed past, then that color, along with its vertex, has to be stored explicitly. We provide algorithms for a graph that is streaming in different variants of the one-pass vertex arrival streaming model, viz. the {\sc Vertex Arrival} ({\sc VA}), {Vertex Arrival With Degree Oracle} ({\sc VAdeg}), {\sc Vertex Arrival in Random Order} ({\sc VArand}) models, with special focus on the random order model. We also provide matching lower bounds for most of the cases. The mainstay of our work is in showing that the properties of a random order stream can be exploited to design streaming algorithms for estimating the number of conflicting edges. We have also obtained a lower bound, though not matching the upper bound, for the random order model. Among all the three models vis-a-vis this problem, we can show a clear separation of power in favor of the {\sc VArand} model.
