We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Institute of Advanced Study

Dr Daniel Paulusma

Exploiting Network Structure to obtain Faster Algorithms

We study discrete optimization problems originating from Computer Science, Economics and Mathematics. For many of these problems we do not know how to solve them efficiently. Our primary example of such a computationally hard problem lies in the area of Frequency Assignment, where the aim is to enable the growth and sustained development of telecommunication networks. Given an emerging information society and global economy, a crucial task for frequency assignment authorities is to minimize the total number of frequencies that must be assigned to a network of transmitters in such a way that frequencies of transmitters close to each other do not overlap.

In order to cope with computationally hard discrete optimization problems we model them as graph problems; a graph is a network consisting of nodes and links between those nodes representing some relationship.  We restrict the input to graphs that can be characterized by some forbidden subgraph and exploit their structure. Many well-known problems that are computationally hard in general can be solved efficiently on such graphs. By researching their structure we can determine the hard problem kernel and increase our understanding on how to deal with the more general inputs. To illustrate the strength of our approach we return to our main application. Let us model transmitters as nodes connected by a link when they are close together. If the resulting graph can be embedded in the plane with non-crossing links, then only four frequencies suffice. This kind of graph is a well-known example of the kind of graphs that fall within our framework.

To find out more about Dr Paulusma please visit his home page on the School of Engineering and Computer Sciences' website: