#
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)

*Abstract:*

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

*Abstract:*

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.