Monday, November 1, 2010
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room MA 005
Lecture - 14:15
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
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.