Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

DOI10.1007/BF01840403zbMath0697.68038OpenAlexW2014864344MaRDI QIDQ911763

Xin He

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840403

zbMATH Keywords

planar graphsperfect graphsPRAM4-coloring algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ Coloring algorithms for \(K_ 5\)-minor free graphs ⋮ A self-stabilizing algorithm for coloring planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On linear-time algorithms for five-coloring planar graphs
• Coloring planar perfect graphs by decomposition
• A fast parallel coloring of planar graphs with five colors
• A batching method for coloring planar graphs
• A characterization of perfect graphs
• An O(N2) algorithm for coloring perfect planar graphs
• Arboricity and Subgraph Listing Algorithms
• Coloring planar graphs in parallel
• A linear 5-coloring algorithm of planar graphs
• An O(logn) parallel connectivity algorithm
• Efficient Planarity Testing
• Finding a Minimum Circuit in a Graph
• The Strong Perfect Graph Conjecture for Planar Graphs