Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
DOI10.1016/0020-0190(94)90104-XzbMATH Open0803.68045MaRDI QIDQ5906512FDOQ5906512
Authors: G. Sajith, Sanjeev Saxena 
Publication date: 3 May 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Recommendations
graph coloringmaximal independent setparallel algorithmsCREW PRAMEREW PRAMoptimal algorithmrooted tree
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
- Faster optimal parallel prefix sums and list ranking
- Improved deterministic parallel integer sorting
- Deterministic parallel list ranking
- A New Parallel Algorithm for the Maximal Independent Set Problem
- Optimal parallel 3-coloring algorithm for rooted trees and its applications
- Data-movement-intensive problems: Two folk theorems in parallel computation revisited
Cited In (9)
- Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
- Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
- Optimal parallel colouring algorithms for totally decomposable graphs
- Parallel \((\Delta +1)\)-coloring of constant-degree graphs
- Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
- Optimal parallel 3-coloring algorithm for rooted trees and its applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906512)
