August 31 – September 5 , 2003, Dagstuhl Seminar 03361

Algorithmic Aspects of Large and Complex Networks


Micah Adler (University of Massachusetts – Amherst, US)
Friedhelm Meyer auf der Heide (Universität Paderborn, DE)
Dorothea Wagner (KIT – Karlsruher Institut für Technologie, DE)

For support, please contact

Dagstuhl Service Team


List of Participants


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.

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.