2-local 4/3-competitive algorithm for multicoloring hexagonal graphs

An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a subgraph of the infinite triangular lattice. Frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weights represent the number of calls to be assigned at vertices. In this paper we present a distributed algorithm for multicoloring hexagonal graphs using only the local clique numbers ω1(v) and ω2(v) at each vertex v of the given hexagonal graph, which can be computed from local information available at the vertex. We prove the algorithm uses no more than ⌈4ω(G)/3⌉ colors for any hexagonal graph G, without explicitly computing the global clique number ω(G). We also prove that our algorithm is 2-local, i.e., the computation at a vertex v∈G uses only information about the demands of vertices whose graph distance from v is less than or equal to 2.