Loading...
Please wait, while we are loading the content...
Fast distributed graph coloring with O(Δ) colors
| Content Provider | Semantic Scholar |
|---|---|
| Author | Marco, Gianluca De Pelc, Andrzej |
| Copyright Year | 2001 |
| Abstract | We consider the problem of deterministic distributed coloring of an n-vertex graph with maximum degree Δ, assuming that every vertex knows a priori only its own label and parameters n and Δ. The aim is to get a fast algorithm using few colors. Linial [17] showed a vertex-coloring algorithm working in time &Ogr;(log* n) and using &Ogr;(Δ2 colors. We improve both the time and the number of colors simultaneously by showing an algorithm working in time &Ogr;(log*(n/Δ)) and using &Ogr;(Δ) colors. This is the first known &Ogr;(Δ)-vertex-coloring distributed algorithm which can work faster than in polylogarithmic time. Our method also gives an edge-coloring algorithm with the number of colors and time as above. On the other hand, it follows from Linial [17] that our time of &Ogr;(Δ)-coloring cannot be improved in general. In addition we show how our method gives fast coloring algorithms in communication models weaker than Linial's. |
| Starting Page | 630 |
| Ending Page | 635 |
| Page Count | 6 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.dia.unisa.it/WSDAAL00/plain/papers/demarco.ps |
| Journal | SODA '01 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
