Bücher von Dorothea Wagner

Thousands of mini computers (comparable to a stick of chewing gum in size), equipped with sensors,are deployed in some terrain or other. After activation thesensorsformaself-organizednetworkandprovidedata,forexampleabout a forthcoming earthquake. The trend towards wireless communication increasingly a?ects electronic devices in almost every sphere of life. Conventional wireless networks rely on infrastructure such as base stations; mobile devices interact with these base stations in a client/server fashion. In contrast, current research is focusing on networks that are completely unstructured, but are nevertheless able to communicate (via several hops) with each other, despite the low coverage of their antennas. Such systems are called sensor orad hoc networks, depending on the point of view and the application. Wireless ad hoc and sensor networks have gained an incredible research momentum.Computerscientistsandengineersofall?avorsareembracingthe area. Sensor networks have been adopted by researchers in many ?elds: from hardware technology to operating systems, from antenna design to databases, from information theory to networking, from graph theory to computational geometry.

The 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000) was held at Waldhaus Jakob, in Konstanz, Germany, on 15{ 17 June 2000. It was organized by the Algorithms and Data Structures Group of the Department of Computer and Information Science, University of K- stanz, and sponsored by Deutsche Forschungsgemeinschaft (DFG) and Univ- sit*atsgesellschaft Konstanz. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions for future research. The workshop looks back on a remarkable tradition of more than a quarter of a century. Previous Workshops have been organized in various places in Europe, and submissions come from all over the world. This year, 57 attendees from 13 di erent countries gathered in the relaxing atmosphere of Lake Constance, also known as the Bodensee. Out of 51 submis- ons, the program committee carefully selected 26 papers for presentation at the workshop. This selection re?ects current research directions, among them graph and network algorithms and their complexity, algorithms for special graph cl- ses, communication networks, and distributed algorithms. The present volume contains these papers together with the survey presented in an invited lecture by Ingo Wegener (University of Dortmund) and an extended abstract of the invited lecture given by Emo Welzl (ETH Zuric * h).

This volume contains the papers accepted for the 4th Workshop on Algorithm Engineering (WAE 2000) held in Saarbruc * ken, Germany, during 5-8 September 2000, together with the abstract of the invited lecture given by Karsten Weihe. The Workshop on Algorithm Engineering covers research on all aspects of the subject. The goal is to present recent research results and to identify and explore directions for future research. Previous meetings were held in Venice (1997), Saarbruc * ken (1998), and London (1999). Papers were solicited describing original research in all aspects of algorithm engineering, including: - Development of software repositories and platforms which allow the use of and experimentation with e?cient discrete algorithms. - Novel uses of discrete algorithms in other disciplines and the evaluation of algorithms for realistic environments. - Methodological issues including standards in the context of empirical - search on algorithms and data structures. - Methodological issues regarding the process of converting user requirements into e?cient algorithmic solutions and implementations. The program committee accepted 16 from a total of 30 submissions. The program committee meeting was conducted electronically. The criteria for sel- tion were originality, quality, and relevance to the subject area of the workshop. Considerable e?ort was devoted to the evaluation of the submissions and to p- viding the authors with feedback. Each submission was reviewed by at least four program committee members (assisted by subreferees). A special issue of the ACM Journal of Experimental Algorithmics will be devoted to selected papers from WAE 2000.

Die Gesellschaft fur Informatik (GI) zeichnet jedes Jahr eine Informatikdissertation durch einen Preis aus. Die Auswahl dieser Dissertation stutzt sich auf die von den Universitaten und Hochschulen fur diesen Preis vorgeschlagenen Dissertationen. Somit sind die Teilnehmer an dem Auswahlverfahren der GI bereits als "e;Preistrager"e; ihrer Hochschule ausgezeichnet.