Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Brief Annoucement: Analysis of an Optimal Bit Complexity Randomised Distributed Vertex Colouring Algorithm
(Extended Abstract)
verfasst von : Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, Akka Zemmari
Erschienen in: Principles of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
= (
V
,
E
) be a simple undirected graph. A vertex
colouring
of
G
assigns colours to each vertex in such a way that neighbours have different colours.
In this paper we discuss how efficient (time and bits) vertex colouring may be accomplished by exchange of bits between neighbouring vertices. The distributed complexity of vertex colouring is of fundamental interest for the study and analysis of distributed computing. Usually, the topology of a distributed system is modelled by a graph and paradigms of distributed systems are encoded by classical problems in graph theory; among these classical problems one may cite the problems of vertex colouring, computing a maximal independent set, finding a vertex cover or finding a maximal matching. Each solution to one of these problems is a building block for many distributed algorithms: symmetry breaking, topology control, routing, resource allocation.