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

DOI10.1016/0020-0190(94)90104-XMaRDI QIDQ5906512zbMATH OpenFDO

Authors G. Sajith, Sanjeev Saxena

Publication date 3 May 1994

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

zbMATH Keywords

graph coloringmaximal independent setparallel algorithmsCREW PRAMEREW PRAMoptimal algorithmrooted tree

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)

Recommendations

• Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
• Optimal parallel 3-coloring algorithm for rooted trees and its applications
• scientific article; zbMATH DE number 19774

Cites work

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

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 3-coloring algorithm for rooted trees and its applications
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• scientific article; zbMATH DE number 562727 (Why is no real title available?)
• scientific article; zbMATH DE number 4047152 (Why is no real title available?)
• scientific article; zbMATH DE number 139775 (Why is no real title available?)

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)