A batching method for coloring planar graphs

DOI10.1016/0020-0190(78)90065-0zbMath0395.05032OpenAlexW2060537627MaRDI QIDQ1252864

Richard J. Lipton, Raymond E. Miller

Publication date: 1978

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

Full work available at URL: https://doi.org/10.1016/0020-0190(78)90065-0

zbMATH Keywords

Batching MethodColouring Planar GraphsFinite GraphVertex Colouring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items

Planar graphs with few vertices of small degree, A fast parallel coloring of planar graphs with five colors, A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs, Parallel construction of subdivision hierarchies, Branch-and-bound techniques for the maximum planar subgraph problem^∗, Batch sizes for the batching method of colouring planar maps, Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs, Coloring certain proximity graphs, On linear-time algorithms for five-coloring planar graphs