March 2 – 6 , 1998, Dagstuhl Seminar 98091

Data Structures


I. Munro (Waterloo), S. Näher (Halle), P. Widmayer (ETH Zürich)

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 202



The design and analysis of algorithms is one of the fundamental areas in computer science. This also involves the development of suitable methods for structuring the data to be manipulated by these algorithms. In this way, algorithms and data structures form a unit and the right choice of algorithms and data structures is a crucial step in the solution of many problems. For this reason, the design, analysis and implementation of data structures form a classical field of computer science both in research and teaching.

The development of the research in this area has been influenced by new application fields such as CAD, Geographic Information Systems, Molecular Biology and Genetics. Not only new methods and paradigms, such as randomisation or competitive analysis of algorithms, have been developed, but there is also some shift of interest away from theory, e.g., the classical analysis of asymptotic behaviour of algorithms, to more practical issues, such as implementation problems and the usefulness of algorithms in practical applications. One can observe that more and more researchers in computer science also want to make their results available in form of programs or software packages. This trend is also reflected in important international conferences.


The Fourth Dagstuhl Seminar on Data Structures was attended by 41 people from 11 countries. The workshop brought together researchers from all over the world working on different areas of the field of efficient data structures and algorithms. Quite a few interest groups used the workshop to discuss and develop ongoing and new cooperations. Many interesting results and solutions for theoretical and practical problems were presented.

The explicit consideration of external memory is becoming a major concern. It is crucial for the practical value of algorithms and data structures, and it creates interesting theoretical problems. Accordingly, there have been several contributions of external memory algorithms and data structures for problems in Computational Geometry and Geographic Information Systems.

On the theoretical side, there have been interesting contributions concerning search & graph structures. A particular result on hashing and several results on special-purpose data & search structures and added features (such as distributed, fault-tolerant, concurrent...) extended recent insights and limits in the area. Another remarkable result showed a (nearly) exact bound for planar point location.

The geometric data structure section saw new algorithms concerning mobile robots and unknown terrain. An algorithm that extends by far the limits of known problem sizes has been presented for rectilinear Steiner trees.

An open problem session reviewed Knuth's 60 famous open problems. It turned out that the majority of the problems is still unsettled today.


The workshop helped to identify several tracks of research in data structures that play and will continue to play an important role in the area. The field of algorithms and data structures continues its expansion towards previously undiscovered fields.

As computers influence more and more aspects of our lives, data structures are needed for an ever growing domain of applications, with questions of steadily increasing complexity.

The general task of developing and analysing simple and practical algorithms and data structures remains with us.


The abstracts of the 35 talks are contained in the published Dagstuhl-Seminar-Report 202, which was compiled by Nora Sleumer. Thanks go to the European Community, which supported the participation of 5 young researchers and 2 key note speakers in the framework of its TMR programme. The organisers would like to thank all participants and especially the team of Schloss Dagstuhl for helping to make the workshop a success. The warm atmosphere of the castle supported discussions and the informal exchange of recent results even beyond the personal perspective. This is exactly what "Schloss Dagstuhl" stands for in the community.

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.