On Coloring Unit Disk Graphs

In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.

Ensemble Planning for Digital Audio Broadcasting

Left-to-right tree pattern matching

We propose a new technique to construct left-to-right matching automata for trees. Our method is based on the novel concept of prefix unifcation which is used to compute a certain closure of the pattern set. From the closure a kind of deterministic matching automaton can be derived immediately. We also point out how to perform the construction incrementally which makes our approach suitable for applications in which pattern sets change dynamically, such as in the Knuth-Bendix completion algorithm.

Distance graphs and the T-coloring problem

Abstract The T-coloring problem is, given a graph G = (V, E), a set T of nonnegative integers containing 0, and a ‘span’ bound s ⩾ 0, to compute an integer coloring f of the vertices of G such that |f(ν) − f(w)| ∉ T ∀νw ∈ E and max f − min f ⩽ s. This problem arises in the planning of channel assignments for broadcast networks. When restricted to complete graphs, the T-coloring problem boils down to a number problem which can be solved efficiently for many types of sets T. The paper presents results indicating that this is not the case if the set T is arbitrary. To these ends, the class of distance graphs is introduced, which consists of all graphs G : G ≅ G(A) for some (finite) set of posi…