Optimal Parallel 5-Colouring of Planar Graphs

DOI10.1137/0218020zbMath0688.68068OpenAlexW2035243909MaRDI QIDQ4207597

Krzysztof Diks, Torben Hagerup, Marek Chrobak

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218020

zbMATH Keywords

planar graphvertex colouringEREW PRAMparallel random access machineoptimal colouring algorithm

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) Algorithms in computer science (68W99)

Related Items (12)

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs ⋮ Efficient computation of implicit representations of sparse graphs ⋮ Parallel complexity of partitioning a planar graph into vertex-induced forests ⋮ Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems ⋮ NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems ⋮ Planar orientations with low out-degree and compaction of adjacency matrices ⋮ Optimal parallel 3-coloring algorithm for rooted trees and its applications ⋮ Parallel algorithms with optimal speedup for bounded treewidth ⋮ Optimal parallel algorithms on planar graphs ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ An efficient parallel algorithm for computing a large independent set in a planar graph

This page was built for publication: Optimal Parallel 5-Colouring of Planar Graphs