Improved Streaming Edge Coloring
Improved Streaming Edge Coloring
计算技术、计算机技术
Shiri Chechik,Hongyi Chen,Tianyi Zhang.Improved Streaming Edge Coloring[EB/OL].(2025-04-23)[2025-09-18].https://arxiv.org/abs/2504.16470.点此复制
Given a graph, an edge coloring assigns colors to edges so that no pairs of
adjacent edges share the same color. We are interested in edge coloring
algorithms under the W-streaming model. In this model, the algorithm does not
have enough memory to hold the entire graph, so the edges of the input graph
are read from a data stream one by one in an unknown order, and the algorithm
needs to print a valid edge coloring in an output stream. The performance of
the algorithm is measured by the amount of space and the number of different
colors it uses.
This streaming edge coloring problem has been studied by several works in
recent years. When the input graph contains $n$ vertices and has maximum vertex
degree $\Delta$, it is known that in the W-streaming model, an
$O(\Delta^2)$-edge coloring can be computed deterministically with
$\tilde{O}(n)$ space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an
$O(\Delta^{1.5})$-edge coloring can be computed by a $\tilde{O}(n)$-space
randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang,
2024].
In this paper, we achieve polynomial improvement over previous results.
Specifically, we show how to improve the number of colors to
$\tilde{O}(\Delta^{4/3+\epsilon})$ using space $\tilde{O}(n)$
deterministically, for any constant $\epsilon > 0$. This is the first
deterministic result that bypasses the quadratic bound on the number of colors
while using near-linear space.
展开英文信息
评论