Algorithmic Aspects of Graph Coloring

我们考虑了各种实际情况下，属性（波长，频率，时隙，机器）必须分配给冲突的对象（光数据流，发射机，流量流，作业）在这样一种方式，没有一对冲突的对象接收相同的属性。我们的模型，如图着色问题的情况。一个图由一组表示对象的顶点和一组表示对象之间冲突的无序顶点对（称为边）组成。图着色涉及到用称为颜色的整数标记某个给定图的顶点，使得没有两个相邻的顶点接收相同的颜色。在许多应用中，目标是最小化颜色的数量。自150多年前作为地图着色问题引入以来，图着色一直是一个热门的研究课题。这是因为它的定义非常简单，它的开放问题种类繁多，应用领域众多。每当对象对之间的冲突情况可以用图来建模，并且人们正在寻找相互不冲突的对象的子集中的对象集合的分区时，这可以被视为图着色问题。这适用于经典设置，例如邻近国家（地图着色）或机器上的干扰作业（作业调度），以及适用于更近的设置，例如光网络中的冲突数据流（波长分配）、冲突业务流（时隙分配）或用于广播的干扰发射机和接收机、移动的电话和传感器（频率分配），仅举几例。请注意，即使是现在非常流行的数独游戏的通过时间也可以归结为用9种颜色（整数1到9）对81个顶点（代表数独游戏的81个正方形）的（部分预着色）图进行着色。在经典设置中，着色是离线完成的，因为整个图是已知的，并且不会随时间变化。这个简单的离线图着色概念的许多变体已经被定义和研究，主要是由于对着色的额外限制。我们说明这一点，考虑着色问题的一般框架与频率分配。在这一应用领域，图形用于模拟发射机（接收机、基站）之间的拓扑结构和相互干扰：图形的顶点代表发射机;如果相应的发射机如此接近（或如此强大），如果它们在相同或“相似”的频率信道上广播，则它们可能会干扰，则图形中的两个顶点相邻。实际上的问题是如何将频道分配给发射机，使干扰保持在“可接受的水平”。在许多技术应用中，离线着色不是一个合适的概念，因为必须着色的图形上的完整信息事先并不知道，例如，如果作业一个接一个地进来，并且必须立即在机器上调度，则重新调度是不可能的。在这种情况下，必须考虑着色的另一种变体，即在线图着色。在这种情况下，图是一个顶点接一个顶点地呈现的，一个顶点必须在它进来时被赋予一种颜色，即颜色的选择仅仅基于到目前为止已经揭示的子图的知识。一般来说，最小化颜色的数量是一个NP难问题（在在线设置中甚至更成问题）。这意味着这个问题很可能没有多项式时间（快速）算法（算法可以被视为解决问题的一组指令）。然而，着色问题发生在特定的情况下，额外的限制可能有不同的时间复杂度。因此，我们试图设计和分析算法，解决图着色问题，在我们的建议中所描述的几个变量的上线和离线设置。

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.