June 17 – 22 , 2001, Dagstuhl Seminar 01251

Graph Decompositions and Algorithmic Applications


Andreas Brandstädt (Universität Rostock, DE)
Jeremy P. Spinrad (Vanderbilt University, US)

For support, please contact

Dagstuhl Service Team


List of Participants
Dagstuhl-Seminar-Report 312


The main goal of this seminar is to bring together experts working in various areas of graph decomposition. Given the fast advances in graph decompositions that we have witnessed in the past few years, we believe that it is very important to offer researchers in graph decomposition a forum for the exchange of ideas in the relaxed workshop-like atmosphere that Dagstuhl can offer.

We anticipate strong interaction and a very healthy exchange of ideas that is likely to result in successful applications of graph (and other) decomposition methods to the design of efficient algorithms, and it will have the following aims:

  • extending known graph decompositions such as the modular, the primeval and the homogeneous decomposition
  • new structural insights by studying graph decomposition
  • extending results on the tree structure of graphs and using such results for the design of efficient algorithms
  • new results on the P4 structure of graphs and decompositions related to this concept such as the investigation of p-connected components
  • exchange of information on recent research and stimulation of further research in the direction of graph decompositions and its algorithmic applications.

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.