[home] - [up]


Lectures and Colloquia during the semester



Monday, July 17, 2006

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041           - map -
Lecture - 14:15

Johannes Köbler - HU Berlin

On the Complexity of Graph Isomorphism and Related Problems

Abstract: In this talk we review some recent complexity results for graph isomorphism as well as for related problems as, e.g., computing the automorphism group of a given graph in terms of a generating set of automorphisms or the canonization problem. Graph isomorphism is one of the few remaining problems in NP whose complexity status couldn't be solved by classifying it as being either NP-complete or solvable in P. Nevertheless, for restricted graph classes, GI turned out to be complete for certain complexity classes as, e.g., NC$_1$, L, and some logspace counting classes.


Colloquium - 16:00

Christian Liebchen - TU Berlin

The Zoo of Tree Spanner Problems

Abstract: Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of max-stretch tree spanner problems and of average stretch tree spanner problems.

We propose a unified notation for 20 tree spanner problems. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems.

Moreover, we detect one tree spanner problem for which its complexity status has not been fixed before. We are able to provide an NP-hardness proof. Finally, we are able to improve the inapproximability factor for the classical max-stretch tree spanner problem from $\frac{1+\sqrt{5}}{2}\approx 1.618$ to $2-\varepsilon$. This is achieved by observing that in the case of unweighted graphs the very same problem has been investigated by Galbiati~(2001,~2003).

Joint work with Gregor Wünsch.


[home] - [up] - [top]