Loading...
Please wait, while we are loading the content...
Similar Documents
Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract) (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Grable, David A. Panconesi, A. |
| Description | ) David A. Grable Institut fur Informatik Humboldt-Universitat zu Berlin D-10099 Berlin Germany grable@informatik.hu-berlin.de Alessandro Panconesi y Institut fur Informatik Humboldt-Universitat zu Berlin D-10099 Berlin Germany ale@informatik.hu-berlin.de 1 Introduction Vertex colouring is a much studied problem in combinatorics and computer science for its theoretical as well as its practical aspects. In this paper we are concerned with the "distributed" version of a question stated by Vizing, concerning a Brooks-like theorem for sparse graphs. Roughly, the question asks whether there exist colourings using many fewer than \Delta colours, where \Delta denotes the maximum degree of the graph, provided that some sparsity conditions are satisfied. In this paper we show that such colourings not only exist, but that they can be quickly computed by extremely simple distributed, randomized algorithms. Before stating our results precisely, we review the relevant facts. For any graph G o... |
| File Format | |
| Journal | J. Algorithms |
| Language | English |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Distributed Algorithm Maximum Degree Sparse Graph Extended Abstract Relevant Fact Introduction Vertex Colouring Brooks-like Theorem Delta Colour Computer Science Brooks-vizing Colouring Practical Aspect Sparsity Condition |
| Content Type | Text |
| Resource Type | Article |
