May 23 – 28 , 2004, Dagstuhl Seminar 04221

Robust and Approximative Algorithms on Particular Graph Classes


Andreas Brandstädt (Universität Rostock, DE)
Derek G. Corneil (University of Toronto, CA)
Klaus Jansen (Universität Kiel, DE)
Jeremy P. Spinrad (Vanderbilt University, US)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants


The aim of this seminar was to bring together experts working on robust as well as on approximative graph algorithms. Given the fast advances in various areas of graph algorithms on particular graph classes that we have witnessed in the past few years, we believe that it was very important to offer researchers in these areas a forum for the exchange of ideas in the relaxed workshop-like atmosphere that Dagstuhl always offers.

There was a strong interaction and healthy exchange of ideas which resulted in successful applications of robust and approximative graph algorithms; in particular, the seminar had the following aims:

  • discussing new graph classes where the recognition complexity of a graph class is harder than solving certain basic graph problems on the class;
  • new structural insights by studying the modular and homogeneous decomposition as well as treewidth and clique-width of important graph classes, and the application of these results to the design of robust graph algorithms;
  • parameterized complexity and its influence to the design of efficient approximative algorithms;
  • solving graph problems approximatively by using (non-)linear programming for graph classes where the problems can be solved in polynomial time but the time bound is poor (e.g. network design problems, Maximum Independent Set for perfect graphs).

The most outstanding result of the discussions during the seminar was the proof of the Seese conjecture by combining results of Courcelle and Sang-il Oum.

As always, Schloss Dagstuhl and its stuff provided a very convenient and stimulating environment. The organizers wish to thank all those who helped to make the seminar a fruitful research experience.

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).


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

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.