The local nature of \(\Delta\)-coloring and its algorithmic applications
From MaRDI portal
Publication:1894705
DOI10.1007/BF01200759zbMath0837.68043OpenAlexW2056050680MaRDI QIDQ1894705
Aravind Srinivasan, Alessandro Panconesi
Publication date: 16 April 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200759
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)
Related Items (15)
An anonymous self-stabilizing algorithm for 1-maximal independent set in trees ⋮ Distance edge coloring and collision‐free communication in wireless sensor networks ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ A self-stabilizing algorithm to maximal 2-packing with improved complexity ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Improved distributed \(\Delta\)-coloring ⋮ Almost global problems in the LOCAL model ⋮ Unnamed Item ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Near-optimal, distributed edge colouring via the nibble method ⋮ Almost global problems in the LOCAL model ⋮ Improved algorithms via approximations of probability distributions ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ Local mending ⋮ Vaught’s conjecture and the Glimm-Effros property for Polish transformation groups
Cites Work
- An NC algorithm for Brooks' theorem
- Removing randomness in parallel computation without a processor penalty
- Brooks Coloring in Parallel
- Deterministic coin tossing with applications to optimal parallel list ranking
- A fast parallel algorithm to color a graph with Δ colors
- Parallel Symmetry-Breaking in Sparse Graphs
- A fast parallel algorithm for routing in permutation networks
- Locality in Distributed Graph Algorithms
This page was built for publication: The local nature of \(\Delta\)-coloring and its algorithmic applications
