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