Algorithmic Aspects of Graph Coloring

点击翻译按钮获取中文摘要

We consider a variety of practical situations in which attributes (wavelengths, frequencies, time slots, machines) have to be allocated to conflicting objects (optical data streams, transmitters, traffic streams, jobs) in such a way that no pair of conflicting objects receives the same attribute. We model such situations as graph coloring problems. A graph is given by a set of vertices that represent the objects and a set of unordered pairs of vertices, called edges, representing the conflicts between pairs of objects. Graph coloring involves the labeling of the vertices of some given graph by integers called colors such that no two adjacent vertices receive the same color. In many applications the objective is to minimize the number of colors. Graph coloring has been a popular research topic since its introduction as a map coloring problem more than 150 years ago. Some reasons for this are its appealingly simple definition, its large variety of open problems, and its many application areas. Whenever conflicting situations between pairs of objects can be modeled by graphs, and one is looking for a partition of the set of objects in subsets of mutually non-conflicting objects, this can be viewed as a graph coloring problem. This holds for classical settings such as neighboring countries (map coloring) or interfering jobs on machines (job scheduling), as well as for more recent settings like colliding data streams in optical networks (wavelength assignment), colliding traffic streams (time slot allocation) or interfering transmitters and receivers for broadcasting, mobile phones and sensors (frequency assignment), to name just a few. Note that even the nowadays so immensely popular pass-time of Sudokus comes down to coloring a (partially precolored) graph on 81 vertices (representing the 81 squares of the Sudoku) with 9 colors (the integers 1 to 9).In the classical setting the coloring is done off-line in the sense that the whole graph is known and it does not change over time. Many variants on this simple off-line graph coloring concept have been defined and studied, mainly due to additional restrictions on the coloring. We illustrate this by considering the general framework for coloring problems related to frequency assignment. In this application area graphs are used to model the topology and mutual interference between transmitters (receivers, base stations): the vertices of the graph represent the transmitters; two vertices are adjacent in the graph if the corresponding transmitters are so close (or so strong) that they are likely to interfere if they broadcast on the same or `similar' frequency channels. The problem in practice is to assign the frequency channels to the transmitters in such a way that interference is kept at an `acceptable level'. In many technological applications off-line coloring is not a suitable concept because complete information on the graph one has to color is not known beforehand, e.g. if jobs come in one-by-one and have to be scheduled on machines right away and rescheduling is not possible. In this case one has to consider another variant of coloring, namely on-line graph coloring. In this setting the graph is presented vertex by vertex, and a vertex must irrevocably be assigned a color as it comes in, i.e. the choice of color is only based on the knowledge of the subgraph that has been revealed so far. In general, minimizing the number of colors is an NP-hard problem (it is even more problematic in the on-line setting) . This means that most likely there is no polynomial time ( fast ) algorithm for this problem (an algorithm can be seen as a set of instructions for solving a problem). However, coloring problems occuring in specific situations with extra restrictions might have a different time complexity. Therefore, we try to design and analyse algorithms that solve graph coloring problems both in the on- and off-line setting for several variants as described in our proposal.