| A new type of graph coloring problem arises from the problem of radio channel assignment in Digital Audio Broadcasting (DAB) networks. This type of network consists of transmitters which transmit a number of services, such as radio programs, weather reports, etc. Each service must be given a channel to be transmitted on. No two services on the same transmitter or two interfering transmitters can be given the same channel, but the same service can be transmitted on a single channel if the transmitters interfere. The problem is to assign channels to the services in a minimal way.; This is essentially a graph coloring problem. The transmitters are represented as vertices which are adjacent if the transmitters interfere. For every vertex, v, there is a set of services, Sv. Each service at each vertex must receive a different color. If vertex u is adjacent to vertex v and there exists a service that is in both Su and Sv, then this service can receive the same channel at u and v. However, different services at adjacent vertices must receive different colors. The “colors” represent the channels which must be assigned, and the goal is to minimize the total number of colors used. In some cases, channels can contain more than one service. The problem then changes in the sense that services must be grouped together, and a channel must be assigned to each group.; This thesis presents approximation algorithms for finding such colorings for trees, paths, and cycles. |
