| Article ID: | iaor2009360 |
| Country: | Germany |
| Volume: | 6 |
| Issue: | 1/2 |
| Start Page Number: | 135 |
| End Page Number: | 151 |
| Publication Date: | Jan 1998 |
| Journal: | Central European Journal of Operations Research |
| Authors: | erovnik Janez |
| Keywords: | markov processes |
The problems of assigning frequencies to transmitters can be naturally modeled by generalizations of graph coloring problems. We consider the problem of minimizing the number of constraints violated when the set of available frequencies is fixed. We prove that the Markov chain corresponding to a randomized algorithm for this problem based of the 3-coloring algorithm of Petford and Welsh is ergodic.