Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM

DOI10.1016/0166-218X(94)00128-ZzbMath0854.68040MaRDI QIDQ1917253

Sanjeev Saxena, G. Sajith

Publication date: 7 July 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

vertex colouring

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) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic parallel list ranking
• A Las Vegas RNC algorithm for maximum matching
• An NC algorithm for Brooks' theorem
• Removing randomness in parallel computation without a processor penalty
• Brooks Coloring in Parallel
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• A fast parallel algorithm to color a graph with Δ colors
• A New Parallel Algorithm for the Maximal Independent Set Problem
• A Simpler Parallel Algorithm for Graph Connectivity
• Constructing a Maximal Independent Set in Parallel
• Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees