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

planar graphsNC algorithmsvertex edge coloring

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) Software, source code, etc. for problems pertaining to combinatorics (05-04)

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

(16)

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

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)