PETFORD WELSH TYPE ALGORITHMS FOR FREQUENCY ASSIGNMENT
Dr Janez Zerovnik, University of Ljubljana, Slovenija

Abstract: The problems of assigning frequencies to transmitters can be naturally modelled by generalizations of graph coloring problems. Based on randomized graph coloring algorithm of Petford and Welsh we give algorithms for some frequency assignment problems including the problem of minimizing the span and the problem of 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.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 20th March, 2000.

back