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