Coloring planar graphs in parallel

DOI10.1016/0196-6774(87)90046-0MaRDI QIDQ3776654zbMATH OpenOpenAlexFDO

Authors Joan Boyar, Howard Karloff

Publication date 1987

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(87)90046-0

zbMATH Keywords

NC algorithmsplanar graphsvertex edge coloring

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Improved edge-coloring algorithms for planar graphs
• scientific article; zbMATH DE number 4076639
• An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors
• Fast algorithms for edge-coloring planar graphs
• Efficient parallel algorithms for edge coloring problems

Cited in

(17)

• A fast parallel coloring of planar graphs with five colors
• An NC algorithm for Brooks' theorem
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• Parallel complexity of partitioning a planar graph into vertex-induced forests
• New linear-time algorithms for edge-coloring planar graphs
• The Parallel Complexity of Coloring Games
• A parallel algorithm for solving the coloring problem on trapezoid graphs
• scientific article; zbMATH DE number 4047151 (Why is no real title available?)
• scientific article; zbMATH DE number 4076639 (Why is no real title available?)
• Fast algorithms for edge-coloring planar graphs
• Optimal Parallel 5-Colouring of Planar Graphs
• Colouring perfect planar graphs in parallel
• NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems
• A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
• An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors

This page was built for publication: Coloring planar graphs in parallel

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