A fast parallel coloring of planar graphs with five colors

DOI10.1016/0020-0190(87)90092-5zbMath0653.68069OpenAlexW2016216976MaRDI QIDQ1108037

Joseph (Seffi) Naor

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90092-5

zbMATH Keywords

parallel algorithmscoloring of planar graphs

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)

Related Items (5)

Vertex coloring of a graph for memory constrained scenarios ⋮ Colouring perfect planar graphs in parallel ⋮ Graph coloring on coarse grained multicomputers ⋮ Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs ⋮ An efficient parallel algorithm for computing a large independent set in a planar graph

Cites Work

• Every planar map is four colorable. I: Discharging
• A batching method for coloring planar graphs
• Parallel concepts in graph theory
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Coloring planar graphs in parallel
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A fast parallel coloring of planar graphs with five colors