MPI-INF Logo
Campus Event Calendar

Event Entry

New for: D1, D2, D3, D4, D5

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

Date, Time and Location

Tuesday, 14 January 2014
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

In the Steiner Forest problem, a weighted graph and disjoint subsets of the nodes are given. The task is to select a subset of the edges spanning each subset of small weight. I will review this classic NP-hard problem from a distributed point of view, where the computing entities are the graph's nodes, which initially only know to which of the subsets (if any) they belong and what the weights of there incident edges are. Communication occurs in rounds across the graph's edges, where message size is restricted to O(log n) bits.


This is a conference talk intended for 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 13:47 -- Created document.