Optimal parallel 3-coloring algorithm for rooted trees and its applications

DOI10.1016/0020-0190(92)90045-WzbMath0742.68028OpenAlexW2163058176MaRDI QIDQ1186596

Peter Rajčáni

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90045-w

zbMATH Keywords

graph coloringplanar graphsrooted treesCRCW PRAMoptimal parallel algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (3)

Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach

Cites Work

• Parallel algorithms for fractional and maximal independent sets in planar graphs
• Faster optimal parallel prefix sums and list ranking
• Parallel Symmetry-Breaking in Sparse Graphs
• Optimal Parallel 5-Colouring of Planar Graphs
• Constructing a Maximal Independent Set in Parallel
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimal parallel 3-coloring algorithm for rooted trees and its applications