[home] - [up]

Lectures and Colloquia during the semester

January 28, 2002

Freie Universität Berlin - Institut für Informatik
Takustraße 9, 14195 Berlin
Room 005           - map -
Lecture - 14:15

Martin Aigner - Freie Universität Berlin

Square Ice

In how many ways can n^2 water molecules be arranged in an n x n--block? This famous problem was solved a few years ago by Kuperberg and Zeilberger. I will survey (with some shortcuts) the main parts of the proofs:

Introduction: A wild conjecture

Theme 1: Combinatorics

Theme 2: Statistical Mechanics

Theme 3: Discrete Calculus

Finale: Putting it all together.

Colloquium - 16:00

Martin Kutz - Freie Universität Berlin

Treeifying Posets with Incomparability Constraints

Abstract:   We present an algorithm that extends a poset to a tree satisfying given incomparability constraints. This problem is closely related to tree description languages, which are an important tool in computational linguistics.

More specifically, we are given a poset (X,q) together with a collection D of incomparable pairs in X. The task is to find an extension q' of the order q so that the covering relations of q' form a rooted tree while all pairs in D remain incomparable in q'.

Our algorithm solves this problem in time O(#X (m + #D)), where m is the size of the - possibly sparse - representation of the order q.

[home] - [up] - [top]