Algorithmic Aspects of Large and Complex Networks

Summary

One cornerstone of our modern society is the use of different kinds of networks. Our cities are connec-ted by a network of streets and railways, telecommunication networks including their wireless, mobile components, the internet, and the World Wide Web build the most important infrastructure for com-munication and information worldwide. Designing and managing such networks pose challenging algorithmic problems.
The second Dagstuhl Seminar on ’Algorithmic Aspects of Large and Complex Networks’ brought together 45 researchers (32 Germany, 4 USA, 3 Switzerland, 2 Italy, 1, Slowenia, 1, Poland, 1 Israel, 1 Greece) to discuss recent advances on a huge variety of network problems as described above. Most of the German participants were members of the corresponding DFG research cluster. The purpose of the workshop was to give the opportunity to exchange ideas between researchers working on different areas of complex networks. Interesting talks, fruitful discussions between researchers on different fields and with different background, and the wonderful working and living environment of Schloss Dagstuhl contributed to the success of the workshop. Below we give some examples for the topics considered at the workshop.

Traffic networks.

We discussed the modelling and computation of time tables for large traffic net-works. This included the computation of time tables for trains and airplanes as well as models for individual traffic.

Time dependent networks.

Related to the computation of time tables is the area of time dependent networks. Here we discussed network algorithms that solve variants of standard network problems ( e.g., shortest paths and network flow) on networks that change over time. Basic network services. One of the topics of the workshop was the question how to provide efficient basic services (e.g., routing) for large computer networks.

Mobile and wireless networks.

The design of algorithms for mobile ad hoc networks and sensor networks is one of the challenges at the beginning of the new century. Dangerous jobs (e.g., exploring contaminated terrain) may in future be performed by robots instead of humans. These robots will be connected by wireless ad hoc networks. We discussed models and algorithms for these kinds of networks.