Fast Distributed Algorithms for Brooks–Vizing Colorings

DOI10.1006/JAGM.2000.1097zbMATH Open0962.68137OpenAlexW2607541376MaRDI QIDQ4512574FDOQ4512574

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

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

zbMATH Keywords

vertex coloringmethod of bounded variances

Mathematics Subject Classification ID

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

Cited In (9)

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

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)