scientific article; zbMATH DE number 17674
[For the entire collection see Zbl 0726.00010.] This paper describes a parallel implementation of the greedy colouring algorithm which colours almost all graphs with \(n\) vertices by at most \[ \left(1+{1\over \log_ 2\log_ 2\log_ 2 n}\right){n\over \log_ 2 n} \] colours (the probability that a random graph with \(n\) vertices is coloured by more colours is \(o(n^{-k})\) for each fixed \(k\)). The model of parallel machine is PRIORITY concurrent read concurrent write PRAM. The algorithm has a worst case parallel running time of \(O(\log^ 2_ 2 n \log_ 2\log_ 2 n)\) and uses \(O(n^ 2\log_ 2^{-2}n)\) processors. The number of colours used by the parallel algorithm is roughly the same as the number of colours uses by the sequential greedy algorithm and approximately twice the expected value of the chromatic number of the graph.
- Fast parallel algorithms for coloring random graphs
- scientific article; zbMATH DE number 3935077
- scientific article; zbMATH DE number 4049082
- Removing randomness in parallel computation without a processor penalty
- Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
- A parallel variant of a heuristical algorithm for graph coloring -- corrigendum
- Removing randomness in parallel computation without a processor penalty
- A processor efficient MIS algorithm on random graphs
- Graph coloring on coarse grained multicomputers
- Coloring permutation graphs in parallel
- Parallel graph algorithms that are efficients on average
- The Parallel Complexity of Coloring Games
- Brooks Coloring in Parallel
- scientific article; zbMATH DE number 3841898 (Why is no real title available?)
- scientific article; zbMATH DE number 4049082 (Why is no real title available?)
- The greedy coloring is a bad probabilistic algorithm
- scientific article; zbMATH DE number 1241723 (Why is no real title available?)
- Parallel and On-Line Graph Coloring
- A framework for scalable greedy coloring on distributed-memory parallel computers
- Fast parallel algorithms for coloring random graphs
- A Parallel Graph Coloring Heuristic
- scientific article; zbMATH DE number 1863545 (Why is no real title available?)
- Parallel Algorithms for Colouring Vertices of Graph Using Bit Manipulation
- Parallel vertex colouring of interval graphs
- Coloring k-colorable graphs in constant expected parallel time
- Graphs with tunable chromatic numbers for parallel coloring
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3975003)
