1-local 17/12-competitive Algorithm for Multicoloring Hexagonal Graphs
Rafal Witkowski
Abstract
In the frequency allocation problem we are given a cellular telephone
network whose geographical coverage area is divided into cells where
phone calls are serviced by frequencies assigned to them, so that none
of the pairs of calls emanating from the same or neighboring cells is
assigned the same frequency. The problem is to use the frequencies
efficiently, i.e. minimize the span of used frequencies. The frequency
allocation problem can be regarded as a multicoloring problem on
a weighted hexagonal graph. In this paper we present a 1-local
17/12-competitive distributed algorithm for a multicoloring of hexagonal
graph, thereby improving the competitiveness ratio of previously known
best 1-local 13/9-competitive algorithm.