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, January 26, 2009
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005

Lecture - 14:15

Günter Rote - FU Berlin

Sandpile Methods

We study simple processes that are known as "sandpile models" or "chip-firing games". In this game we successively place single grains of sand on the nodes of a graph, until the pile at some node gets too big and "topples", passing a grain to each adjacent vertex.
I will point out some of the connexions to algebra, physics, combinatorics, dynamical systems, statistics, algorithms, and computational complexity.

Colloquium - 16:00

Jens Schmidt - FU Berlin

A Simple and Certifying Test on the 3-Connectedness of Graphs

It has been over 35 years now that Hopcroft and Tarjan found the first linear-time test that is able to test graphs on being 3-connected. This algorithm is complex and difficult to implement correctly, and even though some new tests were developed over the time there has not been much progress in simplifying it, nor on extending it to give an easy-to-ceck certificate along with its answer to justify it. We propose a new, simple test on the 3-connectedness of graphs that is based on an inductive construction and - in addition - constructs a certificate for graphs that are 3-connected. This certificate can be easily verified.

Letzte Aktualisierung: 19.01.2009