# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, November 1, 2010

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room MA 005

Lecture - 14:15

### Minimum Spanning Trees: Verification and Randomized Construction

Abstract:
The talk sketches a randomized algorithm due to Karger, Klein and Tarjan for computing minimum spanning trees in expected linear time and then focuses on a key subproblem faced by that algorithm, the linear-time verification of minimum spanning trees. More precisely, a new linear-time algorithm due to the speaker is presented for the \emph{tree-path-maxima} problem of, given a tree $T$ with real edge weights and a list of pairs of distinct nodes in $T$, computing for each pair $(u,v)$ on the list a maximum-weight edge on the path in $T$ between $u$ and $v$. Linear-time algorithms for the tree-path-maxima problem were known previously, but the new algorithm may be considered significantly simpler than the earlier solutions. A linear-time algorithm for the tree-path-maxima problem can be used as a component in the Karger-Klein-Tarjan algorithm and implies a linear-time algorithm for the \emph{MST-verification} problem of, given a spanning tree $T$ of an undirected graph $G$ with real edge weights, determining whether $T$ is a minimum-weight spanning tree of~$G$.

Colloquium - 16:00

### Planar Cayley graphs

Abstract:
In this talk I will present a classification of the cubic planar (mostly infinite) Cayley graphs. This turns out to be a very rich class of graphs, comprising 36 infinite families and one sporadic element, and containing surprising examples contradicting earlier beliefs. It turns out that there is an effective enumeration of these graphs, confirming a conjecture of Droms et. al., and each element is effectively computable. This classification implies refinements of Stallings' celebrated theorem for these graphs. I conjecture that such refinements are possible in general. I will assume no prerequisites, but it would be good to know what a Cayley graph is. There will be many pictures.

Letzte Aktualisierung: 25.10.2010