### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2003) *Distributed soft path coloring*.

** BibTeX **

@conference{

Damaschke2003,

author={Damaschke, Peter},

title={Distributed soft path coloring},

booktitle={Lecture Notes in Computer Science, 20th Symposium on Theoretical Aspects of Computer Science STACS'2003, Berlin 27 February-1 March 2003},

isbn={3-540-00623-0},

pages={523-534},

abstract={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.},

year={2003},

keywords={distributed algorithms, graph coloring, locality, randomized algorithms},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 1834

A1 Damaschke, Peter

T1 Distributed soft path coloring

YR 2003

T2 Lecture Notes in Computer Science, 20th Symposium on Theoretical Aspects of Computer Science STACS'2003, Berlin 27 February-1 March 2003

SN 3-540-00623-0

SP 523

OP 534

AB 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.

LA eng

DO 10.1007/3-540-36494-3_46

LK http://dx.doi.org/10.1007/3-540-36494-3_46

OL 30