CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Distributed soft path coloring

Peter Damaschke (Institutionen för datavetenskap, Algoritmer)
Lecture Notes in Computer Science, 20th Symposium on Theoretical Aspects of Computer Science STACS'2003, Berlin 27 February-1 March 2003 (0302-9743). Vol. 2607 (2003), p. 523-534.
[Konferensbidrag, refereegranskat]

Soft coloring of a graph means that only a few adjacent vertices receive the same color. We study soft coloring in the distributed model where vertices are processing units and edges are communication links. We aim at reducing coloring conflicts as quickly as possible over time by recoloring. Basic insights can be obtained already on the simplest topology, a path. We propose a randomized algorithm for 2-coloring the path with optimal decrease of conflicts. Its analysis is based on properties of random strings of brackets. Conflicts can be reduced exponentially faster if extra colors are allowed. Thus we observe the existence of two significantly different types of the problem, with different ways to get rid of conflicts. Later we generalize the results to a broader class of locally checkable labeling problems on enhanced paths, namely labelings by states from a skew-symmetric transition graph. A result for grid coloring is also presented.

Nyckelord: distributed algorithms, graph coloring, locality, randomized algorithms

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1834


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur