The Fifth Colloquium on Mathematics and Computer Science is, singularly, the sixth one in a series of events that began at the University of Versailles Saint-Quentin with the Colloque Arbres in June 1995, then went on to the First and Second Colloquia on Mathematics and Computer Science in September 2000 and 2002, again in Versailles, the third edition being hold in Vienna in 2004 and the fourth in Nacy 2006. These meetings aim try provide a forum for researchers working on the closely related domains of probabilities, trees, algorithms and combinatorics. Basic data structures of Computer Science, such as trees or graphs, can and should be studied from several points of view: as the data structure underlying some algorithms, or as a combinatorial or probabilistic object.
The previous meetings were very well received and established a vivid and increasing cooperation between mathematicians and researchers in computer science. Both communities get their reward from the cooperation. For mathematicians computer science is a rich source of interesting and new structures, which require a systematic approach and provide new insights. For theoretical computer science researcher it is a source of mathematical knowledge and a platform for exchanging problems and for abstract research on theoretical fundamentals. The previous meetings as well as this one showed an ongoing research and an development of new tools and methods, like in probability, combinatorics and singularity analysis. In this sense, the meetings serves as a melting pot for different views, attitudes and cultures.
With the organization of the 2008 Colloquium, we hope to have contributed further progress on topics at the boundary (or closed partly the gap) between probability theory and theoretical computer science. Papers were sought in a wide spectrum of mathematical areas, for instance random trees, stochastic processes, large deviations, branching processes, random walks, discrete probabilities, analytical and enumerative combinatorics, run time analysis of algorithms and data structures, performance evaluation, random generation of combinatorial structures, singularity analysis, logic, number theory, statistics, stochastic geometry and so on. A large Program Committee, guaranteeing wide coverage of subtopics and expertise in a variety of fields, selected 34 papers for a presentation as 30-minute talks and some for a presentation as a poster. Almost all talk presentations appear in this volume of the journal Discrete Mathematics & Theoretical Computer Science. Furthermore, eight one-hour plenary lectures were presented by the following invited speakers (appearing in alphabetical order)
Philippe Chassaing (Université Henri Poincaré, France)
Jean-Francois Le Gall (Université Paris-Sud, France)
Malwina Luczak (The London School of Economics and Political Sience, Great Britain)
Ralph Neininger (Johann Wolfgang Goethe Universität, Germany)
Mathew Penrose (University of Bath, England)
Angelika Steger (ETH Zürich, Switzerland)
Wojciech Szpankowski (Purdue University, USA)
Joseph E. Yukich (Lehigh University, USA).
The papers assembled in this volume offer snapshots of current research. Moreover, some of them, in particular invited talks, include carefully crafted surveys of their field. The variety of topics illustrate the numerous ramifications of the theory of discrete and random discrete structures throughout mathematics and computer science. And they show the interplay of different fields.
I wish to express my gratitude and indebtness to the members of the Program Committee, who I was honoured to chair, to the members of the Organizing Committee, to the invited speakers and to all the authors and participants of the conference contributing to the great success of the conference. Thanks for all the constructive support, fast reports of the referees, sound advice by the organizing committee, help of the editor-in-chief of DMTCS and many more. Especially I like to thank the coorganizers of the meeting, Rudolph Grübel and Ludger Rueschendorf, for sharing the work, Jan Spitzman for his internet support and the edition of this volume, our secretary Mrs. Ceuleman for the autonomous work and Mrs. Riemer at the desk office.
Last but not least, I would like to thank for financial support by the DFG and the Center of Scientific Computing (CSC) in Kiel. Further the Christian-Albrechts-Universität zu Kiel provided substantial help in many respects.
Kiel, September 2008
Uwe Roesler
Chair of the Program Committee
Program Committee
Philippe Chassaing (Université Henri Poincaré, France)
Brigitte Chauvin (Université de Versailles, France)
Michael Drmota (Technische Universität Wien, Austria)
Philippe Flajolet, (INRIA, France)
Danièle Gardy (Université de Versailles, France)
Rudolf Grübel (Leibniz Universität Hannover, Germany)
Uwe Roesler, chair, (Christian-Albrechts-Universität Kiel, Germany)
Ludger Rüschendorf (Albert-Ludwigs-Universität Freiburg, Germany)
Gilles Schaeffer (CNRS, France)
Robert Sedgewick (Princeton University, USA)
Wojciech Szpankowski (Purdue University, USA)
Brigitte Vallée (Université de Caen, France).
