Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, June 16, 2014

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041





Lecture - 14:15

Fedor Fomin - University of Bergen


Minimal separators

Abstract:
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

Maryna Viazovska - Hausdorff Center for Mathematics, Bonn


Minimal energy problems and t-designs on a sphere

Abstract:
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.




Letzte Aktualisierung: 11.06.2014