The local nature of -coloring and its algorithmic applications

DOI10.1007/BF01200759MaRDI QIDQ1894705zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

connected graphcoloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

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

Cites work

• A fast parallel algorithm for routing in permutation networks
• A fast parallel algorithm to color a graph with Δ colors
• An NC algorithm for Brooks' theorem
• Brooks Coloring in Parallel
• Deterministic coin tossing with applications to optimal parallel list ranking
• Locality in Distributed Graph Algorithms
• Parallel Symmetry-Breaking in Sparse Graphs
• Removing randomness in parallel computation without a processor penalty

Cited in

(25)

• Locality in Distributed Graph Algorithms
• Improved distributed delta-coloring
• -list vertex coloring in linear time
• Near-optimal, distributed edge colouring via the nibble method
• Improved algorithms via approximations of probability distributions
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• 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 anonymous self-stabilizing algorithm for 1-maximal independent set in trees
• An efficient distributed algorithm for constructing small dominating sets
• scientific article; zbMATH DE number 7559119 (Why is no real title available?)
• 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)