Experiments with a Randomized Algorithm for a Frequency Assignment Problem

Janez Zerovnik (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

The problems of assigning frequencies to transmitters can be naturally modelled by generalizations of graph coloring problems. We start with a randomized graph coloring algorithm of Petford and Welsh and propose a randomized algorithm for minimizing the number of constraints violated when a set of frequencies available is fixed. Experiments on instances of various types relevant to mobile communication networks are reported.

Le problème de la planification de fréquence se traduit de façon naturelle en une généralisation du problème de coloriage de graphe. En partant d'un algorithme randomizé proposé par Petford and Welsh nous l'adaptons à la minimisation des violations de contraintes induites par la planification de fréquences. Des expérimentations ont été conduites sur des exemples variés significatifs des problèmes de planification cellulaire.

Mots clés: Cellular Telecommunications System; Frequency Assignment Problem; Randomized Heuristics

Mots clés: Heuristique Randomizé; Planification de Fréquences; Réseau Cellulaire de Radiocommunication

Domaines: Informatique [cs]

Janez Zerovnik. Experiments with a Randomized Algorithm for a Frequency Assignment Problem. [Research Report] LIP RR-1997-09, Laboratoire de l'informatique du parallélisme. 1997, 2+15p. ⟨hal-02101949⟩