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.
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
|B1 - 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.
The presentation equipment will consist of a beamer, 2 overhead projectors and a blackboard.
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
Registration for the workshop starts on Monday at 8:30.
|Monday||Nishizeki||Coffee break||Heggernes, Kráµ, Dorn||Lunch||Kratsch, Lokstanov, Zaks, Fraigniaud, Problem session||Welcome party|
|Tuesday||Thilikos||Coffee break||Rossmanith, Oum, Fomin||Lunch||Paul, Telle, Hliněný, Rao||Concert, Banquet|
|Wednesday||Chudnovsky||Coffee break||Todinca, Fiala, Klavľar||Lunch||Kratochvil, Nisse, Seymour, Discussions and problem solving||Farewell party|
|Jan Brousek||University of West Bohemia, Plzen, Czech Republic|
|Roman Cada||University of West Bohemia, Plzen, Czech Republic|
|Maria Chudnovsky||Princeton University/CMI, Princeton, USA|
|Frederic Dorn||University of Bergen, Bergen, Norway|
|Jiri Fiala||Charles University, Prague, Czech Republic|
|Jan Foniok||Charles University, Prague, Czech Republic|
|Fedor Fomin||University of Bergen, Bergen, Norway|
|Pierre Fraigniaud||CNRS and Univ. of Paris Sud, Orsay, France|
|Michel Habib||Liafa Universite, Paris, France|
|Pinar Heggernes||University of Bergen, Bergen, Norway|
|Petr Hlineny||Masaryk University, Brno, Czech Republic|
|Tomas Kaiser||University of West Bohemia, Plzen, Czech Republic|
|Jan Kara||Charles University, Prague, Czech Republic|
|Sandi Klavzar||University of Maribor, Maribor, Slovenia|
|Daniel Kral||Charles University, Prague, Czech Republic|
|Jan Kratochvil||Charles University, Prague, Czech Republic|
|Dieter Kratsch||LITA Universite de Metz, Metz, France|
|Roman Kuzel||University of West Bohemia, Plzen, Czech Republic|
|Martin Loebl||Charles University, Prague, Czech Republic|
|Daniel Lokshtanov||University of Bergen, Bergen, Norway|
|Anna de Mier||Univeristy of Oxford, Oxford, United Kingdom|
|Iain Moffatt||Charles University, Prague, Czech Republic|
|Pavel Nejedly||Charles University, Prague, Czech Republic|
|Takao Nishizeki||Tohoku University, Sendai, Japan|
|Nicolas Nisse||LRI, Univ. of Paris Sud, Orsay, France|
|Sang-il Oum||Georgia Institute of Technology, Atlanta, USA|
|Ondrej Pangrac||Charles University, Prague, Czech Republic|
|Christophe Paul||LIRMM, Montpellier, France|
|Martin Pergel||Charles University, Prague, Czech Republic|
|Andrzej Proskurowski||University of Oregon, Eugene, USA|
|Michael Rao||LITA Universite de Metz, Metz, France|
|Peter Rossmantih||RWTH Aachen University, Aachen, Germany|
|Paul Seymour||Princeton University, Princeton, USA|
|Petr Skovron||Charles University, Prague, Czech Republic|
|Maciej M. Syslo||University of Wroclaw, Wroclaw, Poland|
|Jan Arne Telle||University of Bergen, Bergen, Norway|
|Dimitrios Thilikos||Universitat Politecnica de Catalunya, Barcelona, Spain|
|Ioan Todinca||University of Orleans, Orleans, France|
|Shmuel Zaks||Technion, Haifa, Israel|
|Jose Zamora||Universidad de Chile, Santiago, Chile|