arXiv:2608.08296 · v2

Truly Work-efficient Parallel Deterministic $(Δ+1)$-coloring and Maximal Independent Set

首次提交 2026-08-09 03:10

版本更新 2026-10-27 01:27

雷达观测 2026-10-29 00:35

摘要

We give deterministic parallel algorithms that compute a $(Δ+1)$-coloring and a maximal independent set for a simple graph with $n$ vertices and $m$ edges in $O(n+m)$ work and $O(\mathrm{poly}\log n)$ depth.

作者备注：SOSA27