English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of coloring a given graph using a small number of colorsin several well-established models of computation for big data. These includethe data streaming model, the general graph query model, the massively parallelcomputation (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models ofdistributed computation. On the one hand, we give algorithms with sublinearcomplexity, for the appropriate notion of complexity in each of these models.Our algorithms color a graph $G$ using about $\kappa(G)$ colors, where$\kappa(G)$ is the degeneracy of $G$: this parameter is closely related to thearboricity $\alpha(G)$. As a function of $\kappa(G)$ alone, our results areclose to best possible, since the optimal number of colors is $\kappa(G)+1$.  On the other hand, we establish certain lower bounds indicating thatsublinear algorithms probably cannot go much further. In particular, we provethat any randomized coloring algorithm that uses $\kappa(G)+1$ many colors,would require $\Omega(n^2)$ storage in the one pass streaming model, and$\Omega(n^2)$ many queries in the general graph query model, where $n$ is thenumber of vertices in the graph. These lower bounds hold even when the value of$\kappa(G)$ is known in advance; at the same time, our upper bounds do notrequire $\kappa(G)$ to be given in advance.

Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models