The slides for all lectures are now available.

## Some of the Theory Behind LEDA (slides)

In my first lecture I will give a survey of some of the theory underlying the LEDA system under five headings.- Algorithms
- System Architecture
- Correctness of Geometrical and Network Algorithms
- Correctness of Implementations
- Efficiency

In later lectures I will discuss some of the topics in more detail.

## Certifying Graph Recognition Algorithms (slides)

A recognition algorithm for a class of graphs is certifying if it gives proofs of membership and non-membership. Proofs of membership are typically a particular representation of the graph and proofs of non-membership are typically forbidden subgraphs of some sort. We discuss certifying recognition algorithms for planar graphs (pages 23 -- 68) and interval graphs.## Graph Algorithms and Data Structures (slides1, slides2)

The worst case running time of some graph algorithms can be improved considerably by the use of data structures: Priority queues for shortest path calculations, dynamic trees for maximum f flow, mergeable priorty queues for general weighted matching. Is it worth the effort? We discuss the issue for shortest paths and general weighted matchings.## TSP-based Curve Reconstruction (slides)

We discuss a polynomially solvable case of the Traveling Salesman Problem

Max-Planck-Institut für Informatik

Algorithms and Complexity Group (AG1)

Im Stadtwald

66123 Saarbrücken

Germany