Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 02, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Sabrina Wiedersheim
The problem of finding a spanning tree with few branch vertices (vertices of degree greater than two) is motivated by the design of communication networks: We are interested in sending signals from a single source to many destinations with a minimum number of connections over fiber links (spanning tree) and subject to this with as few sophisticated light splitting switchers (branch vertices) as possible. In graph theoretical terms a best solution of this problem is a spanning tree with at most one branch vertex. These spanning trees are called spanning spiders.
The decision problem whether there is a spanning spider in a given connected graph G= (E,V) is NP-complete. We describe an O(|E| |V| log |V| 2^k) time algorithm testing the existence of a spider through k vertices (1 <= k <= |V|) in G and reconstructing such a spider, provided there exists one. I will also give a brief impression of further results about the minimum number of branch vertices we need to construct a spanning tree in general, spanning snowflakes, Euclidean graphs and conclude with some open questions.
Joint work with Michael Hoffmann.
Automatic MiSe System Software Version 1.4803M | admin login