Computational Complexity

Announcements

Tutors wanted

We are looking for tutors for the course "Grundzüge von Algorithmen und Datenstrukturen" in winter term 2010/11. If you are interested, please contact Prof. Bläser.

Summer Block Course

The Lecture Concrete Mathematics and Combinatorics will start on Monday, August 9th.

Topics for Bachelor's and Master's Theses

If you are interested in a topic for a thesis, please contact any member of the group. The topic below and our list of topics are suggestions of possible topics but not an exhaustive list.

Implementation of Algorithms for Evaluating Graph Polynomials

A graph polynomial is a mapping that maps graphs to a polynomial such that isomorphic graphs are mapped to the same polynomial. The Tutte polynomial is a famous graph polynomial. It maps graphs to polynomials in two variables X and Y. If we plug in values for X and Y we get an abundance of numerical graph invariants. In this way, the Tutte polynomial counts the number of spanning trees, the number of spanning subgraphs, the number of acyclic orientation, the number of k-colorings and many other interesting invariants of a graph.

Evaluating graph polynomials is a hard problem in general, for instance, evaluating the Tutte polynomial and many other graph polynomials are #P-hard for almost all evaluation points.

Not too many implementations that evaluate graph polynomials exist. The goal of this thesis is to implement algorithms for one specific graph polynomial of your or my choice, like the Tutte polynomial, the interlace polynomial or the cover polynomial. The implementations shall be tested and evaluated and compared with other implementations, if they exist. Time critical parts shall be identified with the goal to get improved algorithms and implementations.