| Summary |
Most algorithmic network problems are NP-hard, which means that we cannot expect to solve them in polynomial time in the worst case. However, the typical input instances that arise in practice often have certain favorable properties that make it easier to solve them efficiently. The theory of FPT algorithms is one way to formalize this. Here one defines a certain parameter for the problem at hand (the size of the solution, for instance) and then the goal is to develop an algorithm that runs in time O(f(k) nc) for a constant c, where n is the input size and k is the parameter. Over the past several years, FPT algorithms have been developed for a number of network problems. Most of these results focus on general networks. In this project we will to study FPT algorithms for geometric networks. |
