A fast parallel coloring of planar graphs with five colors

DOI10.1016/0020-0190(87)90092-5MaRDI QIDQ1108037zbMATH OpenOpenAlexFDO

Authors 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

coloring of planar graphsparallel algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A batching method for coloring planar graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Coloring planar graphs in parallel
• Every planar map is four colorable. I: Discharging
• scientific article; zbMATH DE number 3935077 (Why is no real title available?)
• scientific article; zbMATH DE number 3968611 (Why is no real title available?)
• scientific article; zbMATH DE number 3729461 (Why is no real title available?)
• Parallel concepts in graph theory

Cited in

(5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108037)