Campus Event Calendar
Event Entry
What and Who
Improved Distributed Steiner Forest Construction
Christoph Lenzen
Max-Planck-Institut für Informatik - D1
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 14 July 2014
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In the Steiner Forest problem, one is given a weighted simple graph and disjoint subsets of the nodes. The goal is to determine an edge set of small weight so that, for each subset, all of its nodes are connected. I will revisit this problem from a distributed point of view, where computations are performed by the graph's nodes, each of which initially knows only the weight of its incident edges and in which of the sets (if any) it participates. Communication is round-based, where in each round O(log n) bits can be sent over each edge.
This is a conference talk aiming at a non-specialist audience. Please join and enjoy!
Contact
Christoph Lenzen
--email hidden
passcode not visible
logged in users only
Christoph Lenzen, 07/08/2014 14:25
Christoph Lenzen, 07/08/2014 14:23 -- Created document.
Christoph Lenzen, 07/08/2014 14:23 -- Created document.