Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees

DOI10.1016/0020-0190(94)90104-XzbMath0803.68045MaRDI QIDQ5906512

G. Sajith, Sanjeev Saxena

Publication date: 3 May 1994

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

graph coloringparallel algorithmsoptimal algorithmCREW PRAMrooted treemaximal independent setEREW PRAM

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)

Related Items (2)

Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees

Cites Work

• Deterministic parallel list ranking
• Improved deterministic parallel integer sorting
• Data-movement-intensive problems: Two folk theorems in parallel computation revisited
• Optimal parallel 3-coloring algorithm for rooted trees and its applications
• Faster optimal parallel prefix sums and list ranking
• A New Parallel Algorithm for the Maximal Independent Set Problem

This page was built for publication: Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees