2011 | OriginalPaper | Buchkapitel
Weighted Improper Colouring
verfasst von : Julio Araujo, Jean-Claude Bermond, Frédéric Giroire, Frédéric Havet, Dorian Mazauric, Remigiusz Modrzejewski
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study a colouring problem motivated by a practical frequency assignment problem and up to our best knowledge new. In wireless networks, a node interferes with the other nodes the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph
G
where the weights on the edges represent the noise (interference) between the two end-nodes. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted
t
-improper
k
-colouring of
G
is a
k
-colouring of the nodes of
G
(assignment of
k
frequencies) such that the interference at each node does not exceed some threshold
t
. The Weighted Improper Colouring problem, that we consider here consists in determining the weighted
t
-improper chromatic number defined as the minimum integer
k
such that
G
admits a weighted
t
-improper
k
-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where given a number
k
of colours (frequencies) we want to determine the minimum real
t
such that
G
admits a weighted
t
-improper
k
-colouring. We show that both problems are NP-hard and first present general upper bounds; in particular we show a generalisation of Lovász’s Theorem for the weighted
t
-improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either 1 or
M
, for a sufficient big value
M
. Motivated by the original application, we study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes that are at distance 2. Consequently, the problem consists of determining the weighted
t
-improper chromatic number when
G
is the square of a grid and the weights of the edges are 1, if their end nodes are adjacent in the grid, and 1/2 otherwise. Finally, we model the problem using linear integer programming, propose and test heuristic and exact Branch-and-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.