Monday, June 16, 2014
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
For vertices x,y of a graph G, vertex subset S is a minimal x,y-separator if S separates x and y (x and y are in different connected components of G-S) and S is minimal (no proper subset of S separates x and y). Minimal separators are a handy tool to study graph triangulations, in particular the treewidth and the fill-in of graphs. In this talk we overview several applications of minimal separators in parameterized and exact exponential algorithms. We also discuss algorithms enumerating minimal separators.
Colloquium - 16:00
In this talk we will discuss the interrelation between classical optimization problems on spheres S^d such as minimal equal-weight quadratures (spherical designs) and minimal energy problems. In a joint work with A. Bondarenko and D. Radchenko we have proved the existence of certain configurations in S^d which are spherical t-designs with asymptotically minimal number of points and which simultaneously have asymptotically the best separation property. These configurations also provide approximate solutions for a wide class of minimal problems.