Monday, January 26, 2009
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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.