Graph Searching: Theory and Applications
Instructor: Prof. Dimitros Thilikos (National and Kapodistrian University of Athens)
- https://computing.phd.upc.edu/en/events/copy2_of_course-on-approximation-algorithms-for-hard-combinatorial-problems-and-games
- Graph Searching: Theory and Applications
- 2010-07-12T10:00:00+02:00
- 2010-07-14T13:00:00+02:00
- Instructor: Prof. Dimitros Thilikos (National and Kapodistrian University of Athens)
When
Jul 12, 2010 10:00 AM to Jul 14, 2010 01:00 PM (Europe/Madrid / UTC200)
Where
Edifice Ω, room S208 (floor -2), Campus Nord, UPC, Barcelona
Add event to calendar
Dates: Monday July 12th July to Wednesday July 14th
Time: 10-13
Room: TBA
The course is organized under the mobility program for professors in PhD program that got the quality mention of the Spanish Ministry of Education, funded by the Spanish Ministry of Education.
Abstract:
Graph searching can be seen as a game between a fugitive and a set of searchers. The fugitive resides in a system of rooms and corridors represented by some graph G (vertices of G represent rooms while edges represent corridors between rooms). The purpose of searchers is to catch the fugitive who is trying to avoid capture. Depending on the dynamics of searchers and fugitives, phase restrictions, conditions of captures, global restrictions, visibility, etc. we obtain different models. The variants are either application driven motivated by problems in practice, or are inspired by foundational issues in Computer Science and Discrete Mathematics. Currently, the field on graphs searching is rapidly expanding and during the last years several new models, problems or approaches have appeared. In this course, we list and classify the main models and results in this field and we present some of its main theorem and applications in computer science and discrete mathematics.
Contents:
Definitions and main variants: Graph searching games, Node search, Mixed search, Edge search, Some history, Complexity of graph searching, Monotone strategies.
Monotonicity: The monotonicity issue, Node-search, The monotonicity question, Obstructions to graph searching, Expansions.
Proofs and Obstructions: A proof, Obstructions as escape strategies.
More variants: Visible and active, Invisible and lazy, Monotonicity, Visible and lazy, A min-max theorem for hide-outs.
Graph Searching parameters: Tree Decompositions, Path Decompositions, Complexity results.
The connectivity issue: A disconnected strategy, A connected strategy, Connected parameters, The price of connectivity, A continuous variant.
Further challenges: Non-deterministic graph searching, Many fugitives, Marshal grams, Dominating search, Directed graphs, Cops and Robbers, Alternative costs, More search games.
Note: to better organize the course, please confirm your attendance to the LSI secretariat (merce@lsi.upc.edu)
Time: 10-13
Room: TBA
The course is organized under the mobility program for professors in PhD program that got the quality mention of the Spanish Ministry of Education, funded by the Spanish Ministry of Education.
Abstract:
Graph searching can be seen as a game between a fugitive and a set of searchers. The fugitive resides in a system of rooms and corridors represented by some graph G (vertices of G represent rooms while edges represent corridors between rooms). The purpose of searchers is to catch the fugitive who is trying to avoid capture. Depending on the dynamics of searchers and fugitives, phase restrictions, conditions of captures, global restrictions, visibility, etc. we obtain different models. The variants are either application driven motivated by problems in practice, or are inspired by foundational issues in Computer Science and Discrete Mathematics. Currently, the field on graphs searching is rapidly expanding and during the last years several new models, problems or approaches have appeared. In this course, we list and classify the main models and results in this field and we present some of its main theorem and applications in computer science and discrete mathematics.
Contents:
Definitions and main variants: Graph searching games, Node search, Mixed search, Edge search, Some history, Complexity of graph searching, Monotone strategies.
Monotonicity: The monotonicity issue, Node-search, The monotonicity question, Obstructions to graph searching, Expansions.
Proofs and Obstructions: A proof, Obstructions as escape strategies.
More variants: Visible and active, Invisible and lazy, Monotonicity, Visible and lazy, A min-max theorem for hide-outs.
Graph Searching parameters: Tree Decompositions, Path Decompositions, Complexity results.
The connectivity issue: A disconnected strategy, A connected strategy, Connected parameters, The price of connectivity, A continuous variant.
Further challenges: Non-deterministic graph searching, Many fugitives, Marshal grams, Dominating search, Directed graphs, Cops and Robbers, Alternative costs, More search games.
Note: to better organize the course, please confirm your attendance to the LSI secretariat (merce@lsi.upc.edu)
Share: