Sándor P. Fekete -Technische Universität Braunschweig

Algorithms for large sensor networks

Abstract: Decentralized ad-hoc networks are a new and very active field of research. A tremendous amount of work has been done in applied computer science, but so far, work on algorithmic foundations has been limited.

The main objective of project SwarmNet is to address problems that arise in these networks during self-organized setup and operation. The sensor networks we consider consist of a potentially huge number of independent small devices that can communicate only by radio transmission. These devices are generally equipped with very scarce resources like, energy, computing power, and memory. We assume that no central authority and no specialized location hardware like GPS is available. Another assumption is that nodes are not mobile.

Our major goal is to use simple local protocols in order to achieve distributed knowledge of global properties and structures. We develop efficient algorithms that use discrete and geometric structures. In particular, we present distributed methods for recognizing the geometric boundary of a large set of nodes, and for extracting the underlying topology.

This is joint work with Alexander Kroeller (Braunschweig), Stefan Fischer and Dennis Pfisterer (Luebeck).
URL: http://www.swarmnet.de

Colloquium - 16:00

Carsten Schultz - Technische Universität Berlin

Graph colourings, Hom-complexes, and a proof of the Lovász conjecture

Abstract: Lovász' proof of the Kneser conjecture introduced the idea of bounding the chromatic number of a graph from below by properties of topological spaces associated to the graph. In modern language the lower bound employed by Lovász and its proof are best expressed using Hom-complexes. Hom(G,H) is a cellular complex whose vertices are graph homomorphisms from G to H and whose topology captures the way in which homomorphisms can be transformed into each other by local changes. Lovász' lower bound talks about the complexes Hom(K₂,G). He conjectured a similar lower bound involving the complexes Hom(C_2r+1,G), and this has recently been proved by Babson and Kozlov. We review these results and present a new and shorter proof of the theorem by Babson and Kozlov. For this we first translate a topological problem involving Hom-complexes into one involving more manageable spaces, essentially products of spheres. We then discuss methods from Algebraic Topology that solve this problem. This also closes a gap in a result announced by Babson and Kozlov.