Berufungsvortrag Christian Knauer: Augmenting paths to optimize the diameter

06.07.2015
13:00 - 14:15

Ort

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.

Zeit & Ort

06.07.2015, 13:00 - 14:15

Institut für Informatik SR 005