Unit disk graph coloring and its reoptimization

Abstract

A unit disk graph (UDG) is a graph of intersection of a set of unit disks in Euclidean plane. Motivated by frequency assignment problem in telecommunication, we consider minimum vertex coloring of unit disk graphs (ColorUDG) and its reoptimization which are both NP-hard problems. In the first part of the study, the quality of lower and upper bounds on the optimal value of ColorUDG are investigated by conducting empirical tests. Maximum clique is a lower bound for the minimum coloring. Based on some observations, running time improvement is achieved on the existing O(n4.5) maximum clique algorithm. On the other hand, we derive upper bounds by some simple heuristics (sequential algorithms). Two new construction heuristics and a new improvement method are proposed. In the second part, vertex adding/removing reoptimization problems for ColorUDG are defined. Despite the knowledge of the optimum solution of the old instance, we showed that both problems remains NP-hard, therefore some heuristic methods are proposed. The developed reoptimization algorithms, which perform successfully for many instances when applied to randomly generated graphs. Moreover, we modified Brelaz’s sequential coloring algorithm to solve exactly vertex adding reoptimization problem.