Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering (Q5112251): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+A fast and simple randomized parallel algorithm for the maximal independent set problem
+Normal rank
@@ Property / cites work @@
+Coloring graphs with sparse neighborhoods
@@ Property / cites work: Coloring graphs with sparse neighborhoods / rank @@
+Normal rank
@@ Property / cites work @@
+Sublinear Algorithms for (Δ + 1) Vertex Coloring
@@ Property / cites work: Sublinear Algorithms for (Δ + 1) Vertex Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Maximal Matchings and Maximal Independent Sets
+Normal rank
@@ Property / cites work @@
+Locality of not-so-weak coloring
@@ Property / cites work: Locality of not-so-weak coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
+Normal rank
@@ Property / cites work @@
+Deterministic Distributed Vertex Coloring in Polylogarithmic Time
+Normal rank
@@ Property / cites work @@
+Distributed Graph Coloring: Fundamentals and Recent Developments
+Normal rank
@@ Property / cites work @@
+Locally-Iterative Distributed (Δ+ 1)
@@ Property / cites work: Locally-Iterative Distributed (Δ+ 1) / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
+Normal rank
@@ Property / cites work @@
+The Locality of Distributed Symmetry Breaking
@@ Property / cites work: The Locality of Distributed Symmetry Breaking / rank @@
+Normal rank
@@ Property / cites work @@
+An Automatic Speedup Theorem for Distributed Problems
+Normal rank
@@ Property / cites work @@
+A lower bound for the distributed Lovász local lemma
+Normal rank
@@ Property / cites work @@
+The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
+Normal rank
@@ Property / cites work @@
+Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
+Normal rank
@@ Property / cites work @@
+An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
+Normal rank
@@ Property / cites work @@
+An optimal distributed (Δ+1)-coloring algorithm?
@@ Property / cites work: An optimal distributed (Δ+1)-coloring algorithm? / rank @@
+Normal rank
@@ Property / cites work @@
+A Time Hierarchy Theorem for the LOCAL Model
@@ Property / cites work: A Time Hierarchy Theorem for the LOCAL Model / rank @@
+Normal rank
@@ Property / cites work @@
+Concentration of Measure for the Analysis of Randomized Algorithms
+Normal rank
@@ Property / cites work @@
+Balls and bins: A study in negative dependence
@@ Property / cites work: Balls and bins: A study in negative dependence / rank @@
+Normal rank
@@ Property / cites work @@
+(2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
+Normal rank
@@ Property / cites work @@
+An Improved Distributed Algorithm for Maximal Independent Set
+Normal rank
@@ Property / cites work @@
+Parallel \((\Delta +1)\)-coloring of constant-degree graphs
+Normal rank
@@ Property / cites work @@
+Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
+Normal rank
@@ Property / cites work @@
+Probability Inequalities for Sums of Bounded Random Variables
+Normal rank
@@ Property / cites work @@
+Simple distributed \(\Delta+1\)-coloring of graphs
+Normal rank
@@ Property / cites work @@
+Faster Deterministic Distributed Coloring Through Recursive List Coloring
+Normal rank
@@ Property / cites work @@
+Local Computation
@@ Property / cites work: Local Computation / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of distributed graph coloring
@@ Property / cites work: On the complexity of distributed graph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Locality in Distributed Graph Algorithms
@@ Property / cites work: Locality in Distributed Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Low diameter graph decompositions
@@ Property / cites work: Low diameter graph decompositions / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Parallel Algorithm for the Maximal Independent Set Problem
+Normal rank
@@ Property / cites work @@
+A bound on the strong chromatic index of a graph
@@ Property / cites work: A bound on the strong chromatic index of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
+Normal rank
@@ Property / cites work @@
+The local nature of \(\Delta\)-coloring and its algorithmic applications
+Normal rank
@@ Property / cites work @@
+On the Complexity of Distributed Network Decomposition
+Normal rank
@@ Property / cites work @@
+(Delta+1) Coloring in the Congested Clique Model
@@ Property / cites work: (Delta+1) Coloring in the Congested Clique Model / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Polylogarithmic-time deterministic network decomposition and distributed derandomization
+Normal rank
@@ Property / cites work @@
+A new technique for distributed symmetry breaking
@@ Property / cites work: A new technique for distributed symmetry breaking / rank @@
+Normal rank
@@ Property / cites work @@
+A General Upper Bound on the List Chromatic  Number of Locally Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/19m1249527
+Normal rank
@@ Property / OpenAlex ID @@
+W3026254764
@@ Property / OpenAlex ID: W3026254764 / rank @@
+Normal rank