Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
From MaRDI portal
Publication:5419030
DOI10.1137/12088848XzbMath1311.68185OpenAlexW2136185479MaRDI QIDQ5419030
Leonid Barenboim, Michael Elkin, Fabian Kuhn
Publication date: 4 June 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/12088848x
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (17)
Distributed reconfiguration of maximal independent sets ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Near-linear convergence of the random Osborne algorithm for matrix balancing ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Almost global problems in the LOCAL model ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Almost global problems in the LOCAL model ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Distributed algorithms for fractional coloring
This page was built for publication: Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
