A fast parallel algorithm to color a graph with Δ colors

DOI10.1016/0196-6774(88)90006-5zbMath0647.68068OpenAlexW2057950320MaRDI QIDQ3792256

Joseph (Seffi) Naor, Mauricio Karchmer

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90006-5

zbMATH Keywords

parallel processingvertex coloringNC algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

The local nature of \(\Delta\)-coloring and its algorithmic applications ⋮ Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ An NC algorithm for Brooks' theorem ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Graph coloring on coarse grained multicomputers

This page was built for publication: A fast parallel algorithm to color a graph with Δ colors