Christian Knauer, Universität Bayreuth

13:00 - 13:30 Lehrprobe: k-Median Problem

13:30 - 14:15 Augmenting paths to optimize the diameter.

Abstract: We consider the problem of augmenting a graph with n vertices embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present an ex- act algorithm for the cases when the input graph is a path that runs inO(n log3 n) time.