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

Monday Lecture and Colloquium

Monday, June 18, 2012

Technische Universität Berlin
Institut für Mathematik
Str. des 17. Juni 136
10627 Berlin
room MA 041

Lecture - 14:15

Gianpaolo Oriolo - Universitá Tor Vergata

When Fourier-Motzkin meets shortest paths
(on the way to clique covers in claw-free perfect graphs)

We consider polyhedra (systems) of the form Ax\leq b with A a {0,1,-1} matrix, with at most two non-zero element per row, and b integer. We are interested in the existence of integer solutions to the system. It seems that so far this problem has been considered mainly in the Constraint Programming community. The first algorithm for its solution in polynomial time was given Jaffar, Maher, Stuckey and Yap. Their algorithm, as well as later ones, build upon shortest path techniques and algorithms for 2-SAT.
In the talk, we revisit those algorithms with an integer programming angle and simplify their analysis and proofs. We mainly build upon some nice properties of the Fourier-Motzkin elimination scheme. We then apply our results to the problem of finding a minimum weighted (integral) clique cover in a claw-free perfect graphs. This results in an algorithm for the problem that outperforms the previous algorithms.

Joint work with Flavia Bonomo, Claudia Snels and Gautier Stauffer.

Colloquium - 16:00

Roman Glebov - Freie Universität Berlin

On bounded degree spanning trees in the random graph

The appearence of certain spanning subraphs in the random graph is a well-studied phenomenon in probabilistic graph theory. In this talk, we present results on the threshold for the appearence of bounded-degree spanning trees in G(n,p) as well as for the corresponding universality statements. In particular, we show hitting time thresholds for some classes of bounded degree spanning trees.
Joint work with Daniel Johannsen.