Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 04221

Robust and Approximative Algorithms on Particular Graph Classes

( May 23 – May 28, 2004 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



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.

  • Anne Berry (University Blaise Pascal - Aubiere, FR)
  • Hans L. Bodlaender (Utrecht University, NL) [dblp]
  • Andreas Brandstädt (Universität Rostock, DE) [dblp]
  • Kathie Cameron (Wilfrid Laurier University, CA) [dblp]
  • Derek G. Corneil (University of Toronto, CA) [dblp]
  • Bruno Courcelle (University of Bordeaux, FR) [dblp]
  • Elias Dahlhaus (DB Systems GmbH - Frankfurt, DE) [dblp]
  • Ernst de Ridder (Universität Rostock, DE)
  • Jack E. Edmonds (University of Waterloo, CA)
  • Thomas Erlebach (University of Leicester, GB) [dblp]
  • Elaine M. Eschen (West Virginia University - Morgantown, US)
  • Frank Gurski (Heinrich-Heine-Universität Düsseldorf, DE)
  • Michel Habib (University of Montpellier 2, FR)
  • Chinh T. Hoàng (Wilfrid Laurier University, CA) [dblp]
  • Stefan Hougardy (TU Berlin, DE)
  • Klaus Jansen (Universität Kiel, DE) [dblp]
  • Jan Kara (Charles University - Prague, CZ)
  • Irit Katriel (MPI für Informatik - Saarbrücken, DE)
  • Tilo Klembt (Universität Rostock, DE)
  • Ekkehard Köhler (TU Berlin, DE) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Van Bang Le (Universität Rostock, DE) [dblp]
  • Marina Lipshteyn (Haifa University, IL)
  • Suhail Mahfud (Universität Rostock, DE)
  • Gitta Marchand (Universität Kiel, DE)
  • Ross McConnell (Colorado State University, US)
  • Haiko Müller (University of Leeds, GB) [dblp]
  • Rolf Niedermeier (Universität Jena, DE) [dblp]
  • Sang-il Oum (Princeton University, US) [dblp]
  • Michaël Rao (University of Metz, FR)
  • Dieter B. Rautenbach (Universität Bonn, DE) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Natalia Ryabova (Universität Rostock, DE)
  • Ingo Schiermeyer (TU Bergakademie Freiberg, DE) [dblp]
  • Jeremy P. Spinrad (Vanderbilt University, US)
  • R. Sritharan (University of Dayton, US)
  • Anand Srivastav (Christian-Albrechts-Universität zu Kiel, DE) [dblp]
  • Jayme L. Szwarcfiter (Federal University - Rio de Janeiro, BR)
  • Gabriel Valiente (Polytechnic University of Catalonia, ES)
  • Annegret Wagler (Konrad-Zuse-Zentrum - Berlin, DE)

Related Seminars
  • Dagstuhl Seminar 99231: Graph Decompositions and Algorithmic Applications (1999-06-06 - 1999-06-11) (Details)
  • Dagstuhl Seminar 01251: Graph Decompositions and Algorithmic Applications (2001-06-17 - 2001-06-22) (Details)
  • Dagstuhl Seminar 07211: Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007-05-20 - 2007-05-25) (Details)
  • Dagstuhl Seminar 11182: Exploiting graph structure to cope with hard problems (2011-05-01 - 2011-05-06) (Details)
  • Dagstuhl Seminar 14071: Graph Modification Problems (2014-02-09 - 2014-02-14) (Details)