YOUR RESEARCH, IN SIGHT
覆盖计算机全学科，以 AI 为快捷入口。关注方向、作者和关键词，把发现变成持续的研究积累。
时间范围跟随排序：版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常，查看状态 →
Chase Hutton, Adam Melrod
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.
尚无 AI 解读，展示原文摘要
Guy Blelloch, Andrew Brady, Laxman Dhulipala, Jeremy Fineman, Kishen Gowda, Chase Hutton
A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can insert or delete batches of edges, and the goal is to process the entire batch in parallel with work per edge similar to that of a single sequential update and with span (or depth) for the entire batch that is polylogarithmic. In this paper we present work-efficient parallel batch-dynamic algorithms for maintaining a low out-degree orientation of an undirected graph, both in the amortized and worst-case settings. All results herein achieve polylogarithmic depth; the focus of this paper is on minimizing the work, which varies across results. In the amortized setting, we give a parallel batch-dynamic algorithm that maintains a $O(c)$-orientation in $O(\log n)$ work per update in expectation, where $c$ is a known upper bound on the arboricity over the update sequence. Our algorithm has optimal work in expectation. This result is the parallelization of the classic dynamic orientation algorithm of Brodal and Fagerberg [WADS '99], and, in this setting, is a logarithmic factor faster than the best prior parallel amortized algorithm of Liu et al. [SPAA '22]. In the worst-case setting, we give an $O(c+\log n)$-orientation with worst-case expected work per update $O(\log n)$. This is work-efficient, matching the best known sequential dynamic work of Berglin and Brodal [Algorithmica '20], and implies the existence of an $O(c)$-orientation algorithm with $O(\log^2 n)$ worst-case expected work per update. Both of our algorithms also have deterministic bounds with an additional logarithmic factor in the work. Similar to Berglin and Brodal, by adjusting the parameters of our worst-case algorithm, we achieve tradeoffs where the work is faster than $O(\log n)$ in expectation per update but the max out-degree is worse.
尚无 AI 解读，展示原文摘要