Department of Information and Computing Sciences

Utrecht University

the Netherlands

Foto by Ivar Pel

**Research** - Education - Group - Personal - Misc - Contact

- Fixed parameter complexity. Suppose some parameter of our task is small: e.g., we want to solve a facility location problem (for example: find the optimal location of k hospitals on a map such that the maximum time to travel to a hospital is as small as possible; with the map and k given), but the number of facilities to be placed (k) is small. Several tasks become much easier in the case that such a parameter is small. The area of fixed parameter complexity looks at such cases and comes with faster algorithms, but also a mathematical analysis what is, or is not possible to achieve. An overview of some recent investigations into Parameterized complexity can be found here.
- Kernelization: mathematical analysis of preprocessing. A common approach when solving a hard problem is to apply preprocessing before applying computationally slow exact algorithms. The notion of kernelization makes a precise mathematical analysis of this: can we give a guarantee on the result of a `safe and sound' preprocessing method?
- Graphs and networks with a tree-like structure. Many computationally hard problems on graphs and networks appear to become significantly easier if the network (or graph) has a representation with a tree-structure. One of the most successful approaches uses the notions of tree decomposition and treewidth. My work contains algorithms to determine if such tree representations exist, and if so, find them, and look at (improved) methods to exploit these representations.

I participate in the **Center for Complex Systems Studies** of Utrecht University, as member
of the Advisory Board and Associated Member.

I chair the Steering Committee of the Workshop on Graph Theoretic Concepts in Computer Science, a yearly conference, since 1975, and am regular member of program committees of conferences in theoretical computer science, algorithms research, and parameterized algorithms and complexity.

You can find links to most of my papers on DBLP, or on Google Scholar. A number of early technical reports can be found here.