Workshop on Graph Classes, Width Parameters and Optimization

Prague, October 17 - 19, 2005

Organized jointly by DIMATIA and ITI.

The workshop is the second meeting of Workshop on Optimization Problems, Graph Classes and Width Parameters originally arranged at Centre de Recerca Matematica, Bellaterra, Spain in November 15 to 17, 2001


List of participants, workshop schedule and open problems posed by participants of the workshop are available.


Optimization problems on graphs are often expressed in some formalism: logic, algebra, graph rewriting. Sometimes, such formalisms have corresponding classes of graphs for which these problems are efficiently solvable even if intractable in general. Examples of such graph classes are those with bounded "width" parameters: the pre classical bandwidth, classical treewidth and pathwidth, fairly recent branchwidth, and cliquewidth. Often, classes of graphs defined by some structural properties have bounded width parameter values. Exploring these interplay of problems, graphs and width is the main theme of the workshop.

The proposed structure of the workshop includes contributions from 20-30 invited researchers and ample time (and space) for posing and solving problems. To facilitate the latter, we intend to publish the proposed problems on this web page (best if submitted in .html format to us).

We plan to publish the results presented at the workshop as a special issue of Discrete Applied Mathematics (as we have done after the first workshop: DAM 145(2) appeared in the beginning of 2005). All participants will be welcome to submit a paper to this volume.

Conference photo

conference photo

Invited speakers

Maria Chudnovsky (Princeton/CMI): The structure of clawfree graphs
Takao Nishizeki (Tohoku): Partitioning Graphs of Supply and Demand
Dimitrios Thilikos (Barcelona): Layout problems and related width parameters

Program committee

Jan Kratochvil (Charles University)
Andrzej Proskurowski (University of Oregon)
Oriol Serra (Universitat Politecnica de Catalunya, Barcelona)


The workshop will be held at Male Nosticovo divadelko nad Certovkou (Small Nostic Theater), address Nosticova 834/20, 110 00 Praha - Mala Strana (marked B2 in the map). The tram stop nearest to the theater (marked S2) is called "Hellichova" (this station is 8 stops by tram 22 from the stop "Jana Masaryka" that is nearby the dormitory of "Česká katolická charita" where some participants are accommodated).

Computer room and some other activities are located at the Department of Applied Mathematics of Faculty of Mathematics and Physics, Charles University, Prague. The department is marked B1 in the map. The tram stop nearest to the department (marked S1) is "Malostranské square (Malostranské náměstí)".

Building marked B3 is "Michna palace (Michnův palác)" where the concert and banquet will take place.

"Residence Thunovská" in Thunovská street is marked R1 on the map and hotel "Constans" in Břetislavova street is marked R2

Street mapB1 - Department of Applied Mathematics
B2 - Small Nostic Theater
B3 - Michna Palace
S1 - tram station "Malostranské náměstí"
S2 - tram station "Hellichova"
R1 - "Residence Thunovská"
R2 - hotel "Constans"

Detailed map of the surroundings of the Small Nostic Theater. Red line marks path from "Hellichova" tram station to the theater.

Map of theater surroundings

The presentation equipment will consist of a beamer, 2 overhead projectors and a blackboard.

Participation and costs

Participation is by invitation only. To inquire please contact Jan Kratochvil or Jiri Fiala.

There is no fee charged for invited attendees. Please, register at latest by September 15, 2005, otherwise we cannot guarantee the accommodation.

Workshop schedule

Registration for the workshop starts on Monday at 8:30.

9:3010:3011:00 12:3014:30 18:00
MondayNishizekiCoffee break Heggernes, Kráµ, DornLunch Kratsch, Lokstanov, Zaks, Fraigniaud, Problem session Welcome party
TuesdayThilikosCoffee break Rossmanith, Oum, FominLunch Paul, Telle, Hliněný, RaoConcert, Banquet
WednesdayChudnovskyCoffee break Todinca, Fiala, KlavľarLunch Kratochvil, Nisse, Seymour, Discussions and problem solvingFarewell party

List of participants

Jan BrousekUniversity of West Bohemia, Plzen, Czech Republic
Roman CadaUniversity of West Bohemia, Plzen, Czech Republic
Maria ChudnovskyPrinceton University/CMI, Princeton, USA
Frederic DornUniversity of Bergen, Bergen, Norway
Jiri FialaCharles University, Prague, Czech Republic
Jan FoniokCharles University, Prague, Czech Republic
Fedor FominUniversity of Bergen, Bergen, Norway
Pierre FraigniaudCNRS and Univ. of Paris Sud, Orsay, France
Michel HabibLiafa Universite, Paris, France
Pinar HeggernesUniversity of Bergen, Bergen, Norway
Petr HlinenyMasaryk University, Brno, Czech Republic
Tomas KaiserUniversity of West Bohemia, Plzen, Czech Republic
Jan KaraCharles University, Prague, Czech Republic
Sandi KlavzarUniversity of Maribor, Maribor, Slovenia
Daniel KralCharles University, Prague, Czech Republic
Jan KratochvilCharles University, Prague, Czech Republic
Dieter KratschLITA Universite de Metz, Metz, France
Roman KuzelUniversity of West Bohemia, Plzen, Czech Republic
Martin LoeblCharles University, Prague, Czech Republic
Daniel LokshtanovUniversity of Bergen, Bergen, Norway
Anna de MierUniveristy of Oxford, Oxford, United Kingdom
Iain MoffattCharles University, Prague, Czech Republic
Pavel NejedlyCharles University, Prague, Czech Republic
Takao NishizekiTohoku University, Sendai, Japan
Nicolas NisseLRI, Univ. of Paris Sud, Orsay, France
Sang-il OumGeorgia Institute of Technology, Atlanta, USA
Ondrej PangracCharles University, Prague, Czech Republic
Christophe PaulLIRMM, Montpellier, France
Martin PergelCharles University, Prague, Czech Republic
Andrzej ProskurowskiUniversity of Oregon, Eugene, USA
Michael RaoLITA Universite de Metz, Metz, France
Peter Rossmantih RWTH Aachen University, Aachen, Germany
Paul SeymourPrinceton University, Princeton, USA
Petr SkovronCharles University, Prague, Czech Republic
Maciej M. SysloUniversity of Wroclaw, Wroclaw, Poland
Jan Arne TelleUniversity of Bergen, Bergen, Norway
Dimitrios ThilikosUniversitat Politecnica de Catalunya, Barcelona, Spain
Ioan TodincaUniversity of Orleans, Orleans, France
Shmuel ZaksTechnion, Haifa, Israel
Jose ZamoraUniversidad de Chile, Santiago, Chile

March 2005
Jan Kratochvil, Jiri Fiala