Orientations of planar graphs with applications

by Stefan Felsner.
We will study various types of orientations of planar graphs (Schnyder woods and relatives). These orientations have lots of applications, mainly in geometric representations of planar graphs. In the lectures we show many examples and present some intriguing open problems.

Slides : lecture 1, lecture 2, lecture 3, lecture 4.

Input-sensitive enumerations

by Petr Golovach and Mathieu Liedloff.
As a natural extension on research in exact exponential-time algorithms, an approach for constructing enumeration algorithms, called input-sensitive, which measures the running time in the input length, has found growing interest. Due to the number of objects to enumerate (in the worst case), the algorithms typically have exponential running time. Input-sensitive enumeration is strongly related to lower and upper combinatorial bounds on the maximum number of objects to be enumerated for an input of size n. In the course we survey main techniques that are used in this field.

Slides : slide 1, slide 2, slide 3.

Ideas for approximation algorithms: Matchings, Edge-colorings and the Travelling Salesman

by András Sebő.
The first part of the course and preliminary exercises wish to equalize the knowledge of the audience in some fundamental knowledge of classical combinatorial optimization (mainly matching and matroid theory) in an interactive way, alternating between lecture and exercise solving style. I will count only on knowledge of an introductory course in graph theory or optimization.

Some of the most important classical tools of combinatorial optimization, like matching or matroid theory, have been recently used in various approximation algorithms. The course wishes to introduce the tools themselves, and show some ideas that lead to efficient applications involving 40 years old celebrated conjectures.

Handout and the slides : lecture 1 (ppt), lecture 1 (pdf), lecture 2 (ppt), lecture 2 (pdf), lecture 3 (ppt), lecture 3 (pdf), lecture 4 (ppt), lecture 4 (pdf)

Enumerational approach and concepts in theoretical computer science and engineering

by Takeaki Uno.
While lot of research has been done on Algorithms and Complexity on optimization and decision problems, little attention has been given to enumeration problems. An enumeration problem is one where we are interested in listing all the solutions. For instance, one may be interested in knowing all the 2-connected induced subgraphs of size k. Enumeration problems are ubiquitous in several areas from database theory to biology including areas such as data mining, AI, combinatorial game theory or network design. As the number of objects to list can be arbitrarily large compared to the size of the input, the time complexity of enumeration algorithms is measured with respect to the input and the output (such algorithms are called output-sensitive in contrast to the approach - input-sensitive - followed by Petr Golovach’s lecture). In this lecture we will introduce ideas and techniques - such as reverse search or amortized analysis - for solving enumeration problems and will also pick examples from different areas.

Slides : slide 1 (Monday 1), slide 2 (Monday 2), slide 4 (Thuesday 1), slide 5, slide 6 (Thuesdy 2), slide 7, slide 8, slide 9.

Problem session

Report

Blix theme adapted by David Gilbert, powered by PmWiki