Graph coloring on coarse grained multicomputers

DOI10.1016/S0166-218X(02)00424-9zbMath1029.68114OpenAlexW2059440927MaRDI QIDQ1408826

Jens Gustedt, Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jan Arne Telle

Publication date: 25 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00424-9

zbMATH Keywords

Parallel algorithmsGraph algorithmsGraph coloringCoarse grained multicomputers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A framework for scalable greedy coloring on distributed-memory parallel computers ⋮ Iterative computations with ordered read-write locks ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast parallel coloring of planar graphs with five colors
• An NC algorithm for Brooks' theorem
• Brooks Coloring in Parallel
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm to color a graph with Δ colors
• A Parallel Graph Coloring Heuristic
• New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
• Parallelism in random access machines
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS

This page was built for publication: Graph coloring on coarse grained multicomputers