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 in...
详细信息
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-localdistributed algorithm for multicoloring triangle-free hexagonal graphs using only the local clique numbers omega(1)(v) and omega(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 [5omega(G)/4] + 3 colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number omega(G). Hence the competitive ratio of the algorithm is 5/4. (C) 2004 Elsevier B.V. All rights reserved.
暂无评论