The local nature of -coloring and its algorithmic applications
From MaRDI portal
Publication:1894705
DOI10.1007/BF01200759zbMATH Open0837.68043OpenAlexW2056050680MaRDI QIDQ1894705FDOQ1894705
Authors: Alessandro Panconesi, Aravind Srinivasan 
Publication date: 16 April 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200759
Recommendations
- Locally-iterative Distributed (Δ + 1)-coloring and Applications
- Local coloring: new observations and new reductions
- On the local colorings of graphs
- A note on local colorings of graphs
- A note on local coloring of graphs
- On locally-perfect colorings
- Local \(k\)-colorings of graphs and hypergraphs
- \(k\)-local colorings of graphs
- NP-completeness of local colorings of graphs
- scientific article; zbMATH DE number 2188610
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)
Cites Work
- Locality in Distributed Graph Algorithms
- A fast parallel algorithm to color a graph with Δ colors
- Parallel Symmetry-Breaking in Sparse Graphs
- Deterministic coin tossing with applications to optimal parallel list ranking
- Removing randomness in parallel computation without a processor penalty
- A fast parallel algorithm for routing in permutation networks
- An NC algorithm for Brooks' theorem
- Brooks Coloring in Parallel
Cited In (25)
- Improved distributed delta-coloring
- Locality in Distributed Graph Algorithms
- \(\Delta \)-list vertex coloring in linear time
- Near-optimal, distributed edge colouring via the nibble method
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Improved algorithms via approximations of probability distributions
- Distributed coloring in sparse graphs with fewer colors
- A self-stabilizing algorithm to maximal 2-packing with improved complexity
- Local nature of Brooks' colouring for degree 3 graphs
- Local coloring: new observations and new reductions
- Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
- Brooks Coloring in Parallel
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- An experimental analysis of simple, distributed vertex coloring algorithms
- Almost global problems in the LOCAL model
- Vaught’s conjecture and the Glimm-Effros property for Polish transformation groups
- Distance edge coloring and collision-free communication in wireless sensor networks
- An efficient distributed algorithm for constructing small dominating sets
- An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
- Title not available (Why is that?)
- Fast Distributed Algorithms for Brooks–Vizing Colorings
- Almost global problems in the LOCAL model
- Improved distributed \(\Delta\)-coloring
- Local mending
This page was built for publication: The local nature of \(\Delta\)-coloring and its algorithmic applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894705)
