2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs |
| |
Authors: | Petra Šparl Janez ?erovnik |
| |
Affiliation: | a Faculty of Civil Engineering, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia b Institute of Mathematics, Physics and Mechanics, Jadranska 19, Department of Theoretical Computer Science, 1111 Ljubljana, Slovenia c Faculty of Mechanical Engineering, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia |
| |
Abstract: | 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. The distributed frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weight vector represents the number of calls to be assigned at vertices. In this paper we present a 2-local distributed algorithm for multicoloring triangle-free 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 that the algorithm uses no more than colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number ω(G). Hence the competitive ratio of the algorithm is 5/4. |
| |
Keywords: | Graph algorithms Approximation algorithms Graph coloring Frequency planning Cellular networks 2-local distributed algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|