Fast Distributed Algorithms for Brooks–Vizing Colorings

DOI10.1006/JAGM.2000.1097MaRDI QIDQ4512574zbMATHOpenAlexFDO

Authors David A. Grable, Alessandro Panconesi

Publication date 5 November 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2000.1097

zbMATH Keywords

vertex coloringmethod of bounded variances

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• An experimental analysis of simple, distributed vertex coloring algorithms
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• Distributed graph coloring in a few rounds
• scientific article; zbMATH DE number 2119716
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds

Cited in

(9)

• scientific article; zbMATH DE number 2119716 (Why is no real title available?)
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Distributed coloring algorithms for triangle-free graphs
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
• On the complexity of distributed graph coloring with local minimality constraints
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• An experimental analysis of simple, distributed vertex coloring algorithms

This page was built for publication: Fast Distributed Algorithms for Brooks–Vizing Colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4512574)