GRASTA Workshop on Graph Searching 2009

Dedicated to Gena Hahn

The third Workshop on Graph Searching, Theory and Applications was held 5th-9th October 2009 in hotel Hubertus located in the Valtice chateau, Valtice, Czech Republic.
Conference Photo by Valtice chateau

Lednice-Valtice Area is one of the Czech UNESCO heritage sites. Valtice is a beautiful baroque chateau from the 17th century. More information about the chateau and the area can be found on and on Wikipedia.

The workshop hotel is located directly in the left wing of the chateau. A guided tour of the chateau interiors and historical expositions is planned.

The area is well-known as a centre of vineculture in south Moravia. The tradition of winegrowing thrieves in its many vineyards, wine cellars and collections. One of the wine cellars is located directly at the hotel.


Monday Arrival
18:00 Dinner
20:00 Welcome party
Tuesday 10:00-12:00 D. Thilikos: "Graph Searching Tutorial, Part I", intended for PhD students and newcomers to the topic
12:00 Lunch
14:00-16:00 D. Thilikos: "Graph Searching Tutorial, Part II"
18:00 Dinner
Wednesday 9:00-10:00 P. Pralat: "Chasing robbers on random graphs: The zigzag theorem"
10:00-11:00 Open prolems
12:00 Lunch
14:00-14:30 S. Ordyniak: "Complexity and Monotonicity of Domination Search Games"
15:00-17:00 Discussions
17:00 Progress report
18:00 Dinner
Thursday 9:00-9:30 I. Adler: "Games for width parameters and monotonicity"
10:00-11:00 Discussions
11:00 Progress report
12:00 Lunch
15:00 Excursion to Lednice
19:00 Dinner
Friday 9:00 F. Mazoit: "Monotonicity in graph searching games"
10:00-11:00 Discussions
11:00 Final report
12:00 Lunch


Dimitrios M. Thilikos: Graph Searching Tutorial (7MB PDF presentation). Also see the exercises (PDF).

Pawel Pralat: Chasing robbers on random graphs: The zigzag theorem (1MB PDF presentation).

Pawel Pralat: Cleaning random d-regular graphs with brushes and Brooms (2MB PDF presentation).

Problem sessions

Transcript (PDF) of the problems (by N. Nisse) and scanned notes from the first sessions: Page 1, Page 2, Page 3.

Travel instructions

Valtice is a small town located 50 km south of Brno, 100 km from Bratislava (Slovakia), 100 km from Vienna (Austria) and 200 km from Prague, near the borders with Austria and Slovakia.

The nearest bigger city Břeclav is just 10 km east of Valtice with bus and train connections approx. once an hour. Břeclav is reachable by direct trains from Brno, Bratislava, Vien and Prague (direct or via Brno). The on-line timetables of Czech Railways are available at (also English version). For most of the trains (incl. all local trains) it is best to buy the tickets in the station. Some trains (i.e. EC, SC) may require a seat reservation.

If you plan to come by train, take a train to Břeclav and there take a local train to Valtice (direction Znojmo), take off at Valtice-mesto station and from there walk cca 1km to the city center and the chateau.

The chateau has GPS coordinates 48°44'23.248"N, 16°45'22.315"E. Do not confuse the Valtice chateau with tha chateau Belveder Valtice, which is off city center, near the train station.

You can find basic information about visiting Czech Republic on the site


Accommodation is provided directly in the hotel Hubertus, the price for one night is approximately 40 EUR. However, we will be able to help the participants with local expenses.

The hotel provides free wireless Internet.


Photo gallery

Grasta01.jpg Grasta02.jpg Grasta03.jpg Grasta04.jpg Grasta05.jpg Grasta06.jpg Grasta07.jpg Grasta08.jpg Grasta09.jpg Grasta10.jpg Grasta11.jpg Grasta12.jpg Grasta13.jpg Grasta14.jpg Grasta15.jpg Grasta16.jpg Grasta17.jpg Grasta18.jpg Grasta19.jpg Grasta20.jpg Grasta21.jpg Grasta22.jpg Grasta23.jpg Grasta24.jpg Grasta25.jpg Grasta26.jpg Grasta27.jpg Grasta28.jpg Grasta29.jpg Grasta30.jpg Grasta31b.jpg Grasta31.jpg Grasta32.jpg Grasta33.jpg Grasta34.jpg Grasta35.jpg Grasta36.jpg wine-gallery.jpg

The organizers of GRASTA 2009
Last change 12th November 2009