Workshop on Graph Classes, Width Parameters and Optimization

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

News

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

Focus

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

Invited speakers

Program committee

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

Location

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 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

	9:30	10:30	11:00	12:30	14:30	18:00
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

List of participants