Fast distributed graph coloring with \(O(\Delta)\) colors (Q2768357)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Fast distributed graph coloring with \(O(\Delta)\) colors |
scientific article; zbMATH DE number 1699280
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Fast distributed graph coloring with \(O(\Delta)\) colors |
scientific article; zbMATH DE number 1699280 |
Statements
24 March 2002
0 references
distributed graph
0 references
coloring
0 references
Fast distributed graph coloring with \(O(\Delta)\) colors (English)
0 references
The problem considered in this paper is to color graphs with \(n\) vertices and maximum degree \(\Delta\) in deterministic distributed way, assuming that each vertex only knows its own label and parameters \(n\) and \(\Delta\). The authors presented an algorithm running in time \(O(\log^*(n /\Delta))\) and using \(O(\Delta)\)-vertex-colors.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].
0 references
