Seminar Logik, Komplexität, Spiele: Strukturkomplexität von Graphen und Graph Searching Games

SS 2010

Anmeldung

Sie können sich bis zum 7. Februar per Email an seminar [AT] logic.rwth-aachen.de für das Seminar anmelden. Bitte geben Sie dazu Ihren vollständigen Namen, Matrikelnummer, Studiengang, Fachsemester und Ihre Vorkenntnisse (insbesondere an unserem Lehrgebiet besuchte Vorlesungen) an.

Kurzentschlossene, die sich vor dem 14. Januar anmelden, werden bereits am 15. Januar verständigt, ob sie einen Platz erhalten.

Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt.

Zeitplan

03.05. Gliederung
31.05. Ausarbeitung
14.06. Endgültige Fassung
21.06. Folien

Programm

Montag, 19. July
10:00 10:45 Mieke Kuschnerus DAG-Weite
10:50 11:35 Katinka Becker Kelly-Weite
11:40 12:25 Nikolai Thiemo Pape Entanglement

Inhalt

Many graph-theoretic problems that are difficult on general graphs can be easily solved on graphs that are “simple” in a certain sense, e.g., on graphs that resemble trees. There are several measures for simplicity (or complexity) of graphs such as tree width, clique width, entanglement, and DAG width.

Interestingly, many of these measures can be characterised by so-called graph searching games. These are games in which a group of searchers try to capture a fugitive (think of, e.g., the board game “Scotland Yard”). By adjusting the rules of the game, i.e., by specifying how and when the players are allowed to move through the graph, whether the players can see the others' positions or moves, or by requiring the searchers to capture the fugitive in a special way, we obtain a large variety of games, and the number of searchers needed for capturing the fugitive in some graph yields a measure for a certain aspect of its structural complexity.

In this seminar, we will motivate, introduce and compare several graph parameters and investigate the corresponding searching games. Of special interest will be recent research on transferring well-established notions like tree width, which is defined for undirected graphs, to appropriate and useful notions for directed graphs, and further extensions of the concepts to more general classes of structures like hypergraphs or matroids.

Themen

Thema Vortragende(r) Betreuer(in) Literatur
DAG-Weite Mieke Kuschnerus R. Rabinovich [BDHKO10, HPhD (Ch. 6), HK07]
Kelly-Weite Katinka Becker D. Fischer [HK07, HPhD (Ch. 7), MTV07]
Entanglement Nikolai Thiemo Pape B. Puchala [BG04, BPhD (Ch. 4)]

Literatur

Zuordnung

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich