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

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

Latest revision as of 09:38, 30 July 2024

scientific article; zbMATH DE number 7206138
Language Label Description Also known as
English
Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
scientific article; zbMATH DE number 7206138

    Statements

    Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering (English)
    0 references
    0 references
    0 references
    0 references
    28 May 2020
    0 references
    distributed algorithm
    0 references
    local model
    0 references
    graph coloring
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references