Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Mitarbeiterseminar Logik in der Informatik

Freitag, 16. Dezember 2005, 11:15 Uhr
RUD 25, Raum 4.410

Monotonicity and connectivity for width parameters

Dimitrios M. Thilikos
Universitat Politècnica de Catalunya, Barcelona

The notion of an expansion is a useful framework for defining several known width parameters on graphs. We survey the relation of such parameters with search and conquer games. The goal in these games is to systematically maneuver searches in order to capture a fugitive who flees around the graph or alternatively to organize a gradual occupation of the graph while minimizing specific cost functions. An important question is the so called "monotonicity question": does it cost more to search/conquer a graph if we do not allow the fugitive to visit again "clean" locations? Another question is the "connectivity question": does it cost more to search/conquer a graph if we demand "clean" positions to induce a connected part of the graph? We use expansions to settle the monotonicity and the connectivity questions and we comment related recent results and open problems on their study.

Zurück zur Vortragsübersicht 

Last modified: Tue Dec 6 16:46:43 CET 2005
André Hernich