|
|
Vorlesungsverzeichnis >> Fakultät Wirtschaftsinformatik und Angewandte Informatik >>
|
Tree decompositions, algorithms and games- Dozent/in
- Prof. Dr. Isolde Adler
- Angaben
- Vorlesung
Rein Präsenz
2 SWS, Schein
Zeit und Ort: Di 10:00 - 12:00, WE5/02.020
ab 25.10.2022
- Englischsprachige Informationen:
- Title:
- Tree decompositions, algorithms and games
- Credits: 3
- Prerequisites
- Algorithms and data structures, basic knowledge of predicate
logic, proof techniques, interest in combinatorial games on graphs.
This module is taught in English.
- Contents
- Many classical algorithmic problems on graphs are hard, e.g. NP-hard, in
general. However, they lie at the core of many applications, so they need
to be solved in practice. These problems include the famous Graph
Colouring Problem, and problems such as Hamiltonian Cycle, Independent Set,
Dominating Set, Vertex Cover and many more.
Ideally, we would like to solve these problems exactly and efficiently.
Indeed, many problems become solvable in linear time if we only allow
trees as
inputs. This observation is the starting point of the module. We then
identify more general classes of input graphs that allow solving many
problems efficiently.
For this we make use of so-called tree decompositions of graphs. Tree
decompositions allow us to obtain "tree like" graphs that are more
general than trees but maintain the favourable algorithmic properties
of trees.
In the first part of the module we study tree decompositions via a
cops-and-robber game played on graphs, where the winning strategies for the
cops yield the desired decompositions. We then develop algorithms for tree
decompositions and algorithms to solve problems efficiently making use
of tree
decompositions.
In the second part of the module we introduce monadic second order
logic (MSO) on graphs and we prove a famous theorem by Bruno Courcelle
that shows how to solve all problems expressible in MSO efficiently
on "tree-like" graphs. This includes all aforementioned algorithmic
problems.
We make links to state-of-the-art research in the area and to practical
applications, e.g. in compiler construction.
- Zusätzliche Informationen
- Erwartete Teilnehmerzahl: 30
- Institution: Lehrstuhl für Algorithmen und Komplexitätstheorie
Hinweis für Web-Redakteure:
Wenn Sie auf Ihren Webseiten einen Link zu dieser Lehrveranstaltung setzen möchten, verwenden Sie bitte einen der folgenden Links:Link zur eigenständigen Verwendung Link zur Verwendung in Typo3
|
 |
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|