Computer Science

Colloquium Details

Graph Covers and the Channel Assignment Problem

Abstract

In the talk I will point out a connection, perhaps somewhat surprising, between a theoretical concept of graph covers and a recently intensively studied highly practical problem of assigning radio frequencies to transmitters.

The latter is a widely studied area of research. The task is to assign radio frequencies to transmitters at different locations without interference. A particular subproblem, also referred to as Lambda-coloring of the input graph, asks for assignment of integer values from the range {0,1, ..., Lambda} so that transmitters which are close to each other receive different channels and transmitters which are very close together receive radio channels that are at least two apart. Some results and open problems will be presented, including the recent solution of its computational complexity for fixed Lambda.

The NP-hardness results were obtained via graph covers, a concept which stems from topological and algebraical graph theory (a graph covering projection is an edge-preserving local isomorphism of two graphs). The notion of graph covers appears in so diverse areas as construction of highly symmetric graphs or the theory of local computation. I will conclude the talk by relating a slightly more general concept, namely partial covers (locally injective homomorphisms) to the channel assignment problem, showing that partial covers provide a natural generalization of the linear assignment problem.

The talk is based on joint research with J. Fiala, T. Kloks, A. Proskurowski and J.A. Telle.