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)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/04221
Organizers
- 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)
Contact
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)
